【作者】 王斌；

【导师】 张和平；

【作者基本信息】 兰州大学 ， 运筹学与控制论， 2014， 硕士

【摘要】 本文主要考虑了边传递图直积的独立数也满足Tardif问题等式和一般图的直积与其对应线图的直积独立数分别同时都满足Tardif问题等式的条件.文章正文由三章组成.第一章主要介绍了相关问题的背景.首先说明研究图直积的独立性的意义,然后介绍了一些特殊图在直积下的独立性及其研究状况,在此基础上提出了本文要研究的问题,并简要介绍了文章的主要结果和方法.第二章研究了两个边传递图直积的独立性.关于边传递图与点传递图的联系,由代数图论中的知识我们知道：如果一个没有孤立点的图是边传递的但不是点传递的,则其存在一个二部划分.利用该结果,我们把作直积的边传递图按照边传递图是不是点传递的划分为三类.对于两个边传递图中恰有一个是点传递的情况我们研究其直积独立性用到了交叉相交族中的知识,组合数学的计数方式和二部图的独立集划分等相关结果.最后通过给出一个是边传递但不是点传递的二部图的独立集的特殊划分,我们得到了两个边传递图都不是点传递的情况下直积独立性.第三章简单介绍了两个图作直积与其分别对应的线图也作直积后,两个相应直积图独立性的联系.我们知道没有孤立点边传递图的线图是点传递的,并且两个边传递图的直积的独立性在作线图后的点传递图的直积的独立性都满足Tardif的问题等式.我们利用Hedetniemi猜想的分数形式以及直积图的分数染色数与独立数之间的关系,通过线图性质找到了原图与其线图分别作直积后独立数都满足Tardif的问题等式充要条件.更多还原

【Abstract】 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.更多还原