On the power graph and the reduced power graph of a finite group

In this paper, for a finite group, we investigate to what extent its directed (resp. undirected) reduced power graph determines its directed power graph (resp. reduced power graph). Moreover, we investigate the determination of the orders of the elements of a finite group from its directed (resp. undirected) reduced power graph. Consequently, we show that some classes of finite groups are recognizable from their undirected reduced power graphs. Also, we study the relationship between the isomorphism classes of groups corresponding to the equivalence relations induced by the isomorphism of each of these graphs on the set of all finite groups.     

Triangle-free graphs whose independence number equals the degree

In a triangle-free graph, the neighbourhood of every vertex is an independent set. We investigate the class S of triangle-free graphs where the neighbourhoods of vertices are maximum independent sets. Such a graph G must be regular of degree d=α(G) and the fractional chromatic number must satisfy χ_f(G)=|G|/α(G). We indicate that S is a rich family of graphs by determining the rational numbers c for which there is a graph G∈S with χ_f(G)=c except for a small gap, where we cannot prove the full statement. The statements for c≥3 are obtained by using, modifying, and re-analysing constructions of Sidorenko, Mycielski, and Bauer, van den Heuvel and Schmeichel, while the case c<3 is settled by a recent result of Brandt and Thomassé. We will also investigate the relation between other parameters of certain graphs in S like chromatic number and toughness.     

Optimization of eigenvalue bounds for the independence and chromatic number of graph powers

The $k^{\text{th}}$ power of a graph $G=(V,E)$, $G^k$, is the graph whose vertex set is V and in which two distinct vertices are adjacent if and only if their distance in G is at most k. This article proves various eigenvalue bounds for the independence number and chromatic number of $G^k$ which purely depend on the spectrum of G, together with a method to optimize them. Our bounds for the k-independence number also work for its quantum counterpart, which is not known to be a computable parameter in general, thus justifying the use of integer programming to optimize them. Some of the bounds previously known in the literature follow as a corollary of our main results. Infinite families of graphs where the bounds are sharp are presented as well.     

The power graph of a finite group

The power graph of a group is the graph whose vertex set is the group, two elements being adjacent if one is a power of the other. We observe that non-isomorphic finite groups may have isomorphic power graphs, but that finite abelian groups with isomorphic power graphs must be isomorphic. We conjecture that two finite groups with isomorphic power graphs have the same number of elements of each order. We also show that the only finite group whose automorphism group is the same as that of its power graph is the Klein group of order 4.     

On the global offensive alliance number of a graph

An offensive alliance in a graph Γ=(V,E) is a set of vertices S⊂V where for each vertex v in its boundary the majority of vertices in v’s closed neighborhood are in S. In the case of strong offensive alliance, strict majority is required. An alliance S is called global if it affects every vertex in V?S, that is, S is a dominating set of Γ. The global offensive alliance numberγ_o(Γ) is the minimum cardinality of a global offensive alliance in Γ. An offensive alliance is connected if its induced subgraph is connected. The global-connected offensive alliance number, γ_co(Γ), is the minimum cardinality of a global-connected offensive alliance in Γ.In this paper we obtain several tight bounds on γ_o(Γ) and γ_co(Γ) in terms of several parameters of Γ. The case of strong alliances is studied by analogy.     

On the Soluble Graph of a Finite Simple Group

The maximal independent sets of the soluble graph of a finite simple group G are studied and their independence number is determined. In particular, it is shown that this graph in many cases has an independent set with three vertices.     

An algorithm for calculating the independence and vertex-cover polynomials of a graph

The independence polynomial, ω(G,x)=∑w_kx^k, of a graph, G, has coefficients, w_k, that enumerate the ways of selecting k vertices from G so that no two selected vertices share an edge. The independence number of G is the largest value of k for which w_k≠0. Little is known of less straightforward relationships between graph structure and the properties of ω(G,x), in part because of the difficulty of calculating values of w_k for specific graphs. This study presents a new algorithm for these calculations which is both faster than existing ones and easily adaptable to high-level computer languages.     

Spectral radius of power graphs on certain finite groups

The power graph of a group $G$ is a graph with vertex set $G$ 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 $C_n$ and characterize the graphs for which these bounds are extremal. Further we compute spectra of power graphs of dihedral group $D_{2n}$ and dicyclic group $Q_{4n}$ partially and give bounds for the spectral radii of these graphs.     

Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number

A set of vertices S in a graph G is independent if no neighbor of a vertex of S belongs to S. The independence number α is the maximum cardinality of an independent set of G. A series of best possible lower and upper bounds on α and some other common invariants of G are obtained by the system AGX 2, and proved either automatically or by hand. In the present paper, we report on such lower and upper bounds considering, as second invariant, minimum, average and maximum degree, diameter, radius, average distance, spread of eccentricities, chromatic number and matching number.     

On the independence number of graphs related to a polarity

We investigate the independence number of two graphs constructed from a polarity of . For the first graph under consideration, the Erdős-Rényi graph , we provide an improvement on the known lower bounds on its independence number. In the second part of the paper, we consider the Erdős-Rényi hypergraph of triangles . We determine the exact magnitude of the independence number of , even. This solves a problem posed by Mubayi and Williford [On the independence number of the ErdŐs-RÉnyi and projective norm graphs and a related hypergraph, J. Graph Theory, 56 (2007), pp. 113-127, Open Problem 3].     

Lambda number of the power graph of a finite group

Journal of Algebraic Combinatorics - The power graph $$\Gamma _G$$ of a finite group G is the graph with the vertex set G, where two distinct elements are adjacent if and only if one is a power of...     

On the chromatic number of a random 5‐regular graph

It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is asymptotically almost surely equal to 3, provided a certain four‐variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3‐colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 157–191, 2009     

On the action of a group on a graph, II

This paper is a continuation of the survey by the author (V.I. Trofimov, On the action of a group on a graph, Acta Appl. Math. 29 (1992) 161–170) on some results concerning groups of automorphisms of locally finite vertex-symmetric graphs.     

群与图的对称性

首先对平面图形的对称进行分析和利用其对称群进行量化,进而将此推广到考察一般图的广义"对称性"与图自同构群的关系,最后刻画了无平方因子阶局部本原弧传递图的自同构群结构.     

On a lower bound for the connectivity of the independence complex of a graph

Aharoni, Berger and Ziv proposed a function which is a lower bound for the connectivity of the independence complex of a graph. They conjectured that this bound is optimal for every graph. We give two different arguments which show that the conjecture is false.     

A note on Vizing's independence number conjecture of edge chromatic critical graphs

In 1968, Vizing conjectured that, if G is a Δ-critical graph with n vertices, then α(G)?n/2, where α(G) is the independence number of G. In this note, we verify this conjecture for n?2Δ.