Geodesic
Join of two graphs admits a nowhere-zero $3$-flow
Czechoslovak Mathematical Journal, Tome 64 (2014) no. 2, pp. 433-446 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $G$ be a graph, and $\lambda $ the smallest integer for which $G$ has a nowhere-zero $\lambda $-flow, i.e., an integer $\lambda $ for which $G$ admits a nowhere-zero $\lambda $-flow, but it does not admit a $(\lambda -1)$-flow. We denote the minimum flow number of $G$ by $\Lambda (G)$. In this paper we show that if $G$ and $H$ are two arbitrary graphs and $G$ has no isolated vertex, then $\Lambda (G \vee H) \leq 3$ except two cases: (i) One of the graphs $G$ and $H$ is $K_2$ and the other is $1$-regular. (ii) $H = K_1$ and $G$ is a graph with at least one isolated vertex or a component whose every block is an odd cycle. Among other results, we prove that for every two graphs $G$ and $H$ with at least $4$ vertices, $\Lambda (G \vee H) \leq 3$.
Let $G$ be a graph, and $\lambda $ the smallest integer for which $G$ has a nowhere-zero $\lambda $-flow, i.e., an integer $\lambda $ for which $G$ admits a nowhere-zero $\lambda $-flow, but it does not admit a $(\lambda -1)$-flow. We denote the minimum flow number of $G$ by $\Lambda (G)$. In this paper we show that if $G$ and $H$ are two arbitrary graphs and $G$ has no isolated vertex, then $\Lambda (G \vee H) \leq 3$ except two cases: (i) One of the graphs $G$ and $H$ is $K_2$ and the other is $1$-regular. (ii) $H = K_1$ and $G$ is a graph with at least one isolated vertex or a component whose every block is an odd cycle. Among other results, we prove that for every two graphs $G$ and $H$ with at least $4$ vertices, $\Lambda (G \vee H) \leq 3$.
DOI : 10.1007/s10587-014-0110-0
Classification : 05C20, 05C21, 05C78
Keywords: nowhere-zero $\lambda $-flow; minimum nowhere-zero flow number; join of two graphs 
@article{10_1007_s10587_014_0110_0,
     author = {Akbari, Saieed and Aliakbarpour, Maryam and Ghanbari, Naryam and Nategh, Emisa and Shahmohamad, Hossein},
     title = {Join of two graphs admits a nowhere-zero $3$-flow},
     journal = {Czechoslovak Mathematical Journal},
     pages = {433--446},
     year = {2014},
     volume = {64},
     number = {2},
     doi = {10.1007/s10587-014-0110-0},
     mrnumber = {3277745},
     zbl = {06391503},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0110-0/}
}
TY  - JOUR
AU  - Akbari, Saieed
AU  - Aliakbarpour, Maryam
AU  - Ghanbari, Naryam
AU  - Nategh, Emisa
AU  - Shahmohamad, Hossein
TI  - Join of two graphs admits a nowhere-zero $3$-flow
JO  - Czechoslovak Mathematical Journal
PY  - 2014
SP  - 433
EP  - 446
VL  - 64
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0110-0/
DO  - 10.1007/s10587-014-0110-0
LA  - en
ID  - 10_1007_s10587_014_0110_0
ER  - 
%0 Journal Article
%A Akbari, Saieed
%A Aliakbarpour, Maryam
%A Ghanbari, Naryam
%A Nategh, Emisa
%A Shahmohamad, Hossein
%T Join of two graphs admits a nowhere-zero $3$-flow
%J Czechoslovak Mathematical Journal
%D 2014
%P 433-446
%V 64
%N 2
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0110-0/
%R 10.1007/s10587-014-0110-0
%G en
%F 10_1007_s10587_014_0110_0
Akbari, Saieed; Aliakbarpour, Maryam; Ghanbari, Naryam; Nategh, Emisa; Shahmohamad, Hossein. Join of two graphs admits a nowhere-zero $3$-flow. Czechoslovak Mathematical Journal, Tome 64 (2014) no. 2, pp. 433-446. doi: 10.1007/s10587-014-0110-0

[1] Jaeger, F.: Flows and generalized coloring theorems in graphs. J. Comb. Theory, Ser. B 26 (1979), 205-216. | DOI | MR | Zbl

[2] Jaeger, F.: Nowhere-zero flow problems. Selected Topics in Graph Theory 3 Academic Press, San Diego 71-95 (1988). | MR | Zbl

[3] Luo, R., Zang, W., Zhang, C.: Nowhere-zero $4$-flows, simultaneous edge-colorings, and critical partial Latin squares. Combinatorica 24 (2004), 641-657. | DOI | MR | Zbl

[4] Seymour, P. D.: Nowhere-zero $6$-flows. J. Comb. Theory, Ser. B 30 (1981), 130-135. | DOI | MR | Zbl

[5] Shahmohamad, H.: On minimum flow number of graphs. Bull. Inst. Comb. Appl. 35 (2002), 26-36. | MR | Zbl

[6] Thomassen, C., Toft, B.: Non-separating induced cycles in graphs. J. Comb. Theory, Ser. B 31 (1981), 199-224. | DOI | MR | Zbl

[7] Tutte, W. T.: A contribution to the theory of chromatic polynomials. Can. J. Math. 6 (1954), 80-91. | DOI | MR | Zbl

[8] Tutte, W. T.: On the imbedding of linear graphs in surfaces. Proc. Lond. Math. Soc., II. Ser. 51 (1949), 474-483. | DOI | MR | Zbl

[9] West, D. B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996). | MR | Zbl

Cité par Sources :