共查询到10条相似文献,搜索用时 140 毫秒
1.
The power graph of a group is a graph with vertex set and two distinct vertices are adjacent if and only if one is an integral power of the other. In this paper we find both upper and lower bounds for the spectral radius of power graph of cyclic group and characterize the graphs for which these bounds are extremal. Further we compute spectra of power graphs of dihedral group and dicyclic group partially and give bounds for the spectral radii of these graphs. 相似文献
2.
3.
4.
《Discrete Mathematics》2007,307(9-10):1146-1154
5.
6.
7.
Hailiang Zhang 《Applied Mathematics Letters》2012,25(10):1304-1308
Let us denote the independence polynomial of a graph by . If implies that then we say is independence unique. For graph and if but and are not isomorphic, then we say and are independence equivalent. In [7], Brown and Hoshino gave a way to construct independent equivalent graphs for circulant graphs. In this work we give a way to construct the independence equivalent graphs for general simple graphs and obtain some properties of the independence polynomial of paths and cycles. 相似文献
8.
The inflation of a graph is obtained from by replacing every vertex of degree by a clique and each edge by an edge between two vertices of the corresponding cliques and of in such a way that the edges of which come from the edges of form a matching of . A set of vertices in a graph is a total dominating set, abbreviated TDS, of if every vertex of is adjacent to a vertex in . The minimum cardinality of a TDS of is the total domination number of . In this paper, we investigate total domination in inflated graphs. We provide an upper bound on the total domination number of an inflated graph in terms of its order and matching number. We show that if is a connected graph of order , then , and we characterize the graphs achieving equality in this bound. Further, if we restrict the minimum degree of to be at least , then we show that , with equality if and only if has a perfect matching. If we increase the minimum degree requirement of to be at least , then we show , with equality if and only if every minimum TDS of is a perfect total dominating set of , where a perfect total dominating set is a TDS with the property that every vertex is adjacent to precisely one vertex of the set. 相似文献
9.
10.
The vertex arboricity of a graph is the minimum number of colors required to color the vertices of such that no cycle is monochromatic. The list vertex arboricity is the list-coloring version of this concept. In this note, we prove that if is a toroidal graph, then ; and if and only if contains as an induced subgraph. 相似文献