Skip to main content
added 75 characters in body
Source Link
hbm
  • 1.1k
  • 8
  • 14

For a $2$-edge-connected simple graph $G$ and a tree $T$ of $G$, let $C_e$ be the unique cycle in $T + e$, $e \in E(G) - E(T)$. Define the set $\mathcal{C}(T) = \{C_e | e \in E(G) - E(T)\}$.

Now given a set of cycles $\mathcal{C}$ of $G$, is it possible to decide if $\mathcal{C}$ = $\mathcal{C}(T)$ for some tree $T$ of $G$?

EDIT:

It is easy to see that the following two conditions for $\mathcal{C}$ = $\mathcal{C}(T)$ are necessary :

  1. $|\mathcal{C}|$ = $|E(G)| - |V(G)| + 1|$

  2. The set $\{e \in E(G)|\exists!c\in \mathcal{C}, e \in c \}$ is forest of $G$

    $|\mathcal{C}|$ = $|E(G)| - |V(G)| + 1|$

1') $\cup\mathcal{C} = E(G)$

  1. The set $\{e \in E(G)| e \in c_1\cap c_2 \text{ and } c_1,c_2 \in \mathcal{C} \text{ and }c_1 \ne c_2 \}$ is forest of $G$

My question is: Are they also sufficient?

For a $2$-edge-connected simple graph $G$ and a tree $T$ of $G$, let $C_e$ be the unique cycle in $T + e$, $e \in E(G) - E(T)$. Define the set $\mathcal{C}(T) = \{C_e | e \in E(G) - E(T)\}$.

Now given a set of cycles $\mathcal{C}$ of $G$, is it possible to decide if $\mathcal{C}$ = $\mathcal{C}(T)$ for some tree $T$ of $G$?

EDIT:

It is easy to see that the following two conditions for $\mathcal{C}$ = $\mathcal{C}(T)$ are necessary :

  1. $|\mathcal{C}|$ = $|E(G)| - |V(G)| + 1|$

  2. The set $\{e \in E(G)|\exists!c\in \mathcal{C}, e \in c \}$ is forest of $G$

My question is: Are they also sufficient?

For a $2$-edge-connected simple graph $G$ and a tree $T$ of $G$, let $C_e$ be the unique cycle in $T + e$, $e \in E(G) - E(T)$. Define the set $\mathcal{C}(T) = \{C_e | e \in E(G) - E(T)\}$.

Now given a set of cycles $\mathcal{C}$ of $G$, is it possible to decide if $\mathcal{C}$ = $\mathcal{C}(T)$ for some tree $T$ of $G$?

EDIT:

It is easy to see that the following conditions for $\mathcal{C}$ = $\mathcal{C}(T)$ are necessary :

  1. $|\mathcal{C}|$ = $|E(G)| - |V(G)| + 1|$

1') $\cup\mathcal{C} = E(G)$

  1. The set $\{e \in E(G)| e \in c_1\cap c_2 \text{ and } c_1,c_2 \in \mathcal{C} \text{ and }c_1 \ne c_2 \}$ is forest of $G$

My question is: Are they also sufficient?

added 293 characters in body
Source Link
hbm
  • 1.1k
  • 8
  • 14

For a $2$-edge-connected simple graph $G$ and a tree $T$ of $G$, let $C_e$ be the unique cycle in $T + e$, $e \in E(G) - E(T)$. Define the set $\mathcal{C}(T) = \{C_e | e \in E(G) - E(T)\}$.

Now given a set of cycles $\mathcal{C}$ of $G$, is it possible to decide if $\mathcal{C}$ = $\mathcal{C}(T)$ for some tree $T$ of $G$?

EDIT:

It is easy to see that the following two conditions for $\mathcal{C}$ = $\mathcal{C}(T)$ are necessary :

  1. $|\mathcal{C}|$ = $|E(G)| - |V(G)| + 1|$

  2. The set $\{e \in E(G)|\exists!c\in \mathcal{C}, e \in c \}$ is forest of $G$

My question is: Are they also sufficient?

For a $2$-edge-connected simple graph $G$ and a tree $T$ of $G$, let $C_e$ be the unique cycle in $T + e$, $e \in E(G) - E(T)$. Define the set $\mathcal{C}(T) = \{C_e | e \in E(G) - E(T)\}$.

Now given a set of cycles $\mathcal{C}$ of $G$, is it possible to decide if $\mathcal{C}$ = $\mathcal{C}(T)$ for some tree $T$ of $G$?

For a $2$-edge-connected simple graph $G$ and a tree $T$ of $G$, let $C_e$ be the unique cycle in $T + e$, $e \in E(G) - E(T)$. Define the set $\mathcal{C}(T) = \{C_e | e \in E(G) - E(T)\}$.

Now given a set of cycles $\mathcal{C}$ of $G$, is it possible to decide if $\mathcal{C}$ = $\mathcal{C}(T)$ for some tree $T$ of $G$?

EDIT:

It is easy to see that the following two conditions for $\mathcal{C}$ = $\mathcal{C}(T)$ are necessary :

  1. $|\mathcal{C}|$ = $|E(G)| - |V(G)| + 1|$

  2. The set $\{e \in E(G)|\exists!c\in \mathcal{C}, e \in c \}$ is forest of $G$

My question is: Are they also sufficient?

Source Link
hbm
  • 1.1k
  • 8
  • 14

Fundamental Cycles of a graphs

For a $2$-edge-connected simple graph $G$ and a tree $T$ of $G$, let $C_e$ be the unique cycle in $T + e$, $e \in E(G) - E(T)$. Define the set $\mathcal{C}(T) = \{C_e | e \in E(G) - E(T)\}$.

Now given a set of cycles $\mathcal{C}$ of $G$, is it possible to decide if $\mathcal{C}$ = $\mathcal{C}(T)$ for some tree $T$ of $G$?