关于有限群幂图的强彩虹连通数
|
摘要
图的强彩虹连通数在网络信息安全传输中有重要的应用,由于决定图的强彩虹连通数问题是NP-困难的,因此需要给出一些特殊图的强彩虹连通数的计算方法.该文首先运用图论与群论的相关知识,给出了幂图强彩虹连通数的一些上下界,并且研究了达到界的一些幂图.其次利用这些界给出了循环群、初等交换p-群、二面体群和半二面体群的幂图的强彩虹连通数的计算公式.结果表明,幂图的强彩虹连通数依赖于群的极大对合数及群的极大循环子群数.
Strong rainbow connection number of a graph is an important application in network information security transmission.Since the problem of determining the strong rainbow connectivity number of graphs is NP-hard,it is necessary to give some calculation methods of the strong rainbow connection number for some special graphs.Firstly,using the knowledge of graph theory and group theory,some upper and lower bounds of strong rainbow connection number of the power graph of a group are given,and some power graphs reaching the bounds are studied.Secondly,the formulas for calculating the strong rainbow connection number of the power graph of a cyclic group,an elementary abelian-group,a dihedral group and a semidihedral group are given by using these bounds.The results show that the strong rainbow connection number of the power graph of a group depends on the number of all maximal involutions of the group and the number of all maximal cyclic subgroups of the group.
Strong rainbow connection number of a graph is an important application in network information security transmission.Since the problem of determining the strong rainbow connectivity number of graphs is NP-hard,it is necessary to give some calculation methods of the strong rainbow connection number for some special graphs.Firstly,using the knowledge of graph theory and group theory,some upper and lower bounds of strong rainbow connection number of the power graph of a group are given,and some power graphs reaching the bounds are studied.Secondly,the formulas for calculating the strong rainbow connection number of the power graph of a cyclic group,an elementary abelian-group,a dihedral group and a semidihedral group are given by using these bounds.The results show that the strong rainbow connection number of the power graph of a group depends on the number of all maximal involutions of the group and the number of all maximal cyclic subgroups of the group.
引文
[1] Chartrand G,Johns G L,Mckeon K A,et al.Rainbow connection in graphs[J].Mathematica Bohemica,2008,133:85-98.
[2] Chakraborty S,Fischer E,Matsliah A,et al.Hardness and algorithms for rainbow connection[J].Journal of Combinatorial Optimization,2011,21:330-347.
[3] Li X,Shi Y,Sun Y.Rainbow connections of graphs:a survey[J].Graphs and Combinatorics,2013,29:1-38.
[4]周津名.上三角矩阵环的零因子图的自同构[J].湖南师范大学学报(自然科学版),2018,41(4):85-90.
[5]游兴中.有限群的一类新的共轭类图[J].长沙理工大学学报(自然科学版),2007,4(3):87-92.
[6]罗驰,任永才.共轭类图最多有三条边的有限群[J].四川大学学报(自然科学版),2003,40(4):603-608.
[7]王艳芳,王丽娟.图论与群的凯莱图[J].辽宁师范大学学报(自然科学版),2005,28(2):155-157.
[8]曹树江,居腾霞.哈密尔顿单位凯莱图[J].南通大学学报(自然科学版),2018,17(4):71-76.
[9]谢金华,杨霞,徐尚进.32p阶二面体群的3度Cayley图的正规性[J].广西师范学院学报(自然科学版),2019,36(1):6-12.
[10]Kelareva V,Quinn S J.A combinatorial property and power graphs of groups[J].Contributions to General Algebra,2000,12:229-235.
[11]Chakrabarty I,Ghosh S,Sen M K.Undirected power graphs of semigroups[J].Semigroup Forum,2009,78:410-426.
[12]Bubboloni D,Iranmanesh M A,Shaker S M.Quotient graphs for power graphs[J].Rendiconti del Seminario Matematico della Universitàdi Padova,2017,138:61-89.
[13]Ma X,Feng M,Wang K.The strong metric dimension of the power graph of a finite group[J].Discrete Applied Mathematics,2018,239:159-164.
[14]Ma X,Walls G L,Wang K.Power graphs of(non)orientable genus two[J].Communications in Algebra,2019,47:276-288.
[15]郑涛,郭秀云.幂零群与内幂零群的幂图[J].上海大学学报(自然科学版),2018,24(6):1030-1038.
[16]Abawajy J,Kelareva V,Chowdhury M.Power graphs:A survey[J].Electronic Journal of Graph Theory and Applications,2013,1:125-147.
[17]Ma X,Feng M,Wang K.The rainbow connection number of the power graph of a finite group[J].Graphs and Combinatorics,2016,32:1495-1504.
[18]Polya G,Szego G.Problems and Theorems in Analysis II[M].New York:Springer,1976.
[2] Chakraborty S,Fischer E,Matsliah A,et al.Hardness and algorithms for rainbow connection[J].Journal of Combinatorial Optimization,2011,21:330-347.
[3] Li X,Shi Y,Sun Y.Rainbow connections of graphs:a survey[J].Graphs and Combinatorics,2013,29:1-38.
[4]周津名.上三角矩阵环的零因子图的自同构[J].湖南师范大学学报(自然科学版),2018,41(4):85-90.
[5]游兴中.有限群的一类新的共轭类图[J].长沙理工大学学报(自然科学版),2007,4(3):87-92.
[6]罗驰,任永才.共轭类图最多有三条边的有限群[J].四川大学学报(自然科学版),2003,40(4):603-608.
[7]王艳芳,王丽娟.图论与群的凯莱图[J].辽宁师范大学学报(自然科学版),2005,28(2):155-157.
[8]曹树江,居腾霞.哈密尔顿单位凯莱图[J].南通大学学报(自然科学版),2018,17(4):71-76.
[9]谢金华,杨霞,徐尚进.32p阶二面体群的3度Cayley图的正规性[J].广西师范学院学报(自然科学版),2019,36(1):6-12.
[10]Kelareva V,Quinn S J.A combinatorial property and power graphs of groups[J].Contributions to General Algebra,2000,12:229-235.
[11]Chakrabarty I,Ghosh S,Sen M K.Undirected power graphs of semigroups[J].Semigroup Forum,2009,78:410-426.
[12]Bubboloni D,Iranmanesh M A,Shaker S M.Quotient graphs for power graphs[J].Rendiconti del Seminario Matematico della Universitàdi Padova,2017,138:61-89.
[13]Ma X,Feng M,Wang K.The strong metric dimension of the power graph of a finite group[J].Discrete Applied Mathematics,2018,239:159-164.
[14]Ma X,Walls G L,Wang K.Power graphs of(non)orientable genus two[J].Communications in Algebra,2019,47:276-288.
[15]郑涛,郭秀云.幂零群与内幂零群的幂图[J].上海大学学报(自然科学版),2018,24(6):1030-1038.
[16]Abawajy J,Kelareva V,Chowdhury M.Power graphs:A survey[J].Electronic Journal of Graph Theory and Applications,2013,1:125-147.
[17]Ma X,Feng M,Wang K.The rainbow connection number of the power graph of a finite group[J].Graphs and Combinatorics,2016,32:1495-1504.
[18]Polya G,Szego G.Problems and Theorems in Analysis II[M].New York:Springer,1976.