摘要
给定一个有限群G,群G上的简化幂图是以G的所有元素为顶点集合的一个简单图,其中两个不同的顶点x和y相邻当且仅当〈x〉〈y〉或〈y〉〈x〉.图的独立数是图论中的一个重要的图参数,计算一个图的独立数问题是NP-困难的.该文计算了一些循环群及p-群的简化幂图的独立数.此外,也给出了群简化幂图独立数的上下界,且刻画了达到界简化幂图所对应的有限群.
Given a finite group G,the reduced power graph of G is an undirected graph with vertex set G,and two distinct verticesandare adjacent if and only if〈x〉〈y〉or〈y〉〈x〉.The independence number of a graph is an important parameter in graph theory.The problem of computing the independence number of a graph is NP-hard.This paper computes the independence number of the reduced power graphs of some cyclic groups and some-groups.Moreover,this paper also gives upper and lower bounds for the independence number of a reduced power graph and characterizes the finite groups whose reduced power graphs reach the bounds.
作者
马儇龙
仪钰婷
安佳薇
吴玥雯
MA Xuan-long;YI Yu-ting;AN Jia-wei;WU Yue-wen(School of Science,Xi'an Shiyou University,Xi'an 710065,China)
出处
《南宁师范大学学报（自然科学版）》
2020年第4期9-13,共5页
Journal of Nanning Normal University：Natural Science Edition
基金
国家自然科学基金项目(11801441)
国家级大学生创新创业训练项目(201910705028)。
关键词
简化幂图
独立数
有限群
reduced power graph
independence number
finite group
