|
|||||
|
|
Join of two graphs admits a nowhere-zero 3-flow |
|
| Authors: | Saieed Akbari Maryam Aliakbarpour Naryam Ghanbari Emisa Nategh Hossein Shahmohamad |
| Affiliation: | 1. Department of Mathematical Sciences, Sharif University of Technology; School of Mathematics, Institute for Studies in Theoretical Physics and Mathematics, P.O. Box 19395-5746, Tehran, Iran 2. Department of Computer Engineering, Sharif University of Technology, P.O. Box 19395-5746, Tehran, Iran 3. Department of Electrical Engineering, Sharif University of Technology, P.O. Box 19395-5746, Tehran, Iran 4. Department of Mathematical Sciences, Sharif University of Technology, P.O. Box 19395-5746, Tehran, Iran 5. School of Mathematical Sciences, RIT, Rochester, New York, 14623, USA |
| Abstract: | Let G be a graph, and λ the smallest integer for which G has a nowherezero λ-flow, i.e., an integer λ for which G admits a nowhere-zero λ-flow, but it does not admit a (λ ? 1)-flow. We denote the minimum flow number of G by Λ(G). In this paper we show that if G and H are two arbitrary graphs and G has no isolated vertex, then Λ(G ∨ H) ? 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, Λ(G ∨ H) ? 3. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |