The Path-Positive Property on the Products of Graphs

摘要

The products of graphs discussed in this paper are the following four kinds; the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G_1 and G_2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path-positive graphs. ② If the tensor product is a path-positive graph if and only if the graph G_1 and G_2 are the connected graphs, and the graph G_1 or G_2 has an odd cycle and max{ λ_1μ_1, λ_nμ_m} ≥2 in which λ_1 and λ_n[or μ_1 and μ_m] are maximum and minimum characteristic values of graph G_1[ or G_2], respectively.