Independence In Direct Products Of Edge-transitive Graphs

This paper considers that the independent number in direct products of edge-transitive graphs also satisfies the equations of Tardif’s problem and the conditions that the independent number of direct product of general graphs and corresponding line graph simultaneously satisfies the equations of Tardif’s problem. Body of the article consists of three chapters.The first chapter mainly introduces the background related issues. The first description of the meaning of independence in direct products of graphs, then in-troduces independence in direct products of some special graphs and the research status of these. This paper raises a problem on this basis, and briefly introduces the main results of the article and methods.The second chapter studies the independence in direct products of two edge-transitive graphs. About the connection between edge-transitive graphs and vertex-transitive graphs, by algebraic graph’theory, we know that If a graph has no isolated vertices is edge-transitive but not vertex-transitive, then one has a two part divi-sion. Using this result, we divide direct product of edge-transitive graphs into three categories. For the case that one of two edge-transitive graphs exactly satisfies vertex-transitive, we use the knowledge of cross intersecting family, combinatorial mathematics, the partition of independent sets in bipartite graph. Finally, by giv-ing a special division of independent sets in bipartite graph that is edge-transitive but not vertex-transitive, we obtain the independence in direct products of two edge-transitive graphs that are not vertex-transitive.The third chapter introduces that after making respectively a direct product of two graph and its corresponding line graphs, we contact the independence of two corresponding direct product graphs. We know that the line graphs of edge-transitive graphs is vertex-transitive and the independence in direct products of the line graphs of the edge-transitive graphs also satisfies the equations of Tardif’s problem. By the fractional version of conjecture of Hedetniemi and the relationship between the fractional chromatic number and independence number, we find the sufficient and necessary condition about the independence number in direct products of original graph and its line graph.