图的字典积的整数流(英文)

Flows on lexicographic product of graphs

得到对连通图G1和阶数大于3的图G2,他们的字典积G1[G2]有非零4-流.特别当G2是二部图时,G1[G2]有非零3-流.通过一个完全不同的方法,也得到了如果G1有非零3-流且具有完美匹配或G2有非零3-流,那么G1[G2]有非零3-流.

It is shown that for a nontrivial connected graph G1 and a connected graph G2 of order at least 3, the lexieographie product G1 [ G2 ] of G1 and G2 admits a nowhere - zero 4 - flow in general. Furthermore if G2 is bipartite, then the product admits a nowhere - zero 3 - flow. By a different method we also show that if G1 admits a nowhere - zero 3 - flow and has perfect matehings or G2 admits a nowhere - zero 3 - flow, then the product admits a nowhere - zero 3 - flow.