§ Online Archives §

- Accepted Papers
- Author Index
- Journal Correction
- Back Issues(1973-2005)

New Series (2006~2012)

For a set ${\cal C}$ of
directed circuits of a graph $G$ that form an oriented circuit
double cover, we denote by $I_{\cal C}$ the graph with vertex set
${\cal C}$, in which two circuits $C$ and $ C'$ are connected by $k$
edges if $|\underline{C} \cap \underline{C'}| =k$. Let
$\Phi^*_c(G)={\rm min}\chi_c(I_{\cal C})$, where the minimum is
taken over all the oriented circuit double covers of $G$. It is easy
to show that for any graph $G$, $\Phi_c(G) \leq \Phi^*_c(G)$. On the
other hand, it follows from well-known results that for any integer
$2 \leq k \leq 4$, $\Phi^*_c(G) \leq k$ if and only if $\Phi_c(G)
\leq k$; for any integer $k \geq 1$, $\Phi^*_c(G) \leq 2 +
\frac{1}{k}$ if and only if $\Phi_c(G) \leq 2 + \frac{1}{k}$.

This papers proves that for any rational number $2 \leq r \leq 5$ there
exists a graph $G$ for which $\Phi^*_c(G) = \Phi_c(G) =r$. We also
show that there are graphs $G$ for which $\Phi_c(G) < \Phi^*_c(G)$.

Circuit double cover, circular flow number, edge rooted graph, flow, graph, parallel join, series join

Primary: 60F15

Received: 2010-08-26

Revised :

Accepted: 2010-12-01

Download Full Content

Copyright © Bulletin, Institute of Mathematics, Academia Sinica 2016