Variable neighborhood search for extremal graphs. 22. Extending bounds for independence to upper irredundance

A set of vertices S in a graph G is independent if no neighbor of a vertex of S belongs to S. A set of vertices U in a graph G is irredundant if each vertex v of U has a private neighbor, which may be v itself, i.e., a neighbor of v which is not a neighbor of any other vertex of U. The independence number α (resp. upper irredundance number IR) is the maximum number of vertices of an independent (resp. irredundant) set of G. In previous work, a series of best possible lower and upper bounds on α and some other usual invariants of G were obtained by the system AGX 2, and proved either automatically or by hand. These results are strengthened in the present paper by systematically replacing α by IR. The resulting conjectures were tested by AGX which could find no counter-example to an upper bound nor any case where a lower bound could not be shown to remain tight. Some proofs for the bounds on α carry over. In all other cases, new proofs are provided.     

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.     

Variable neighborhood search for extremal graphs 3

In the set of bicolored trees with given numbers of black and of white vertices we describe those for which the largest eigenvalue is extremal (maximal or minimal). The results are first obtained by the automated system AutoGraphiX, developed in GERAD (Montreal), and verified afterwards by theoretical means.     

Variable neighborhood search for extremal graphs 3

In the set of bicolored trees with given numbers of black and of white vertices we describe those for which the largest eigenvalue is extremal (maximal or minimal). The results are first obtained by the automated system AutoGraphiX, developed in GERAD (Montreal), and verified afterwards by theoretical means.     

Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph

We consider four conjectures related to the largest eigenvalue of (the adjacency matrix of) a graph (i.e., to the index of the graph). Three of them have been formulated after some experiments with the programming system AutoGraphiX, designed for finding extremal graphs with respect to given properties by the use of variable neighborhood search. The conjectures are related to the maximal value of the irregularity and spectral spread in n-vertex graphs, to a Nordhaus–Gaddum type upper bound for the index, and to the maximal value of the index for graphs with given numbers of vertices and edges. None of the conjectures has been resolved so far. We present partial results and provide some indications that the conjectures are very hard.     

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Δ.     

Large minors in graphs with given independence number

A weakening of Hadwiger’s conjecture states that every n-vertex graph with independence number α has a clique minor of size at least . Extending ideas of Fox (2010) [6], we prove that such a graph has a clique minor with at least vertices where c>1/19.2.     

On the independence number of the power graph of a finite group

The power graph ${\Gamma }_G$ of a finite group $G$ is the graph whose vertex set is $G$, two distinct elements being adjacent if one is a power of the other. In this paper, we give sharp lower and upper bounds for the independence number of ${\Gamma }_G$ and characterize the groups achieving the bounds. Moreover, we determine the independence number of ${\Gamma }_G$ if $G$ is cyclic, dihedral or generalized quaternion. Finally, we classify all finite groups $G$ whose power graphs have independence number 3 or $n?2$, where $n$ is the order of $G$.     

Independence number of de Bruijn graphs

In this paper, we give several exact values of the independence number of a de Bruijn graph UB(d,D) and in the other cases, we establish pertinent lower and upper bounds of this parameter. We show that asymptotically, if d is even, the ratio of the number of vertices of a greatest independent set of UB(d,D) is .     

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].     

Ohba’s conjecture for graphs with independence number five

Ohba has conjectured that if G is a k-chromatic graph with at most 2k+1 vertices, then the list chromatic number or choosability of G is equal to its chromatic number χ(G), which is k. It is known that this holds if G has independence number at most three. It is proved here that it holds if G has independence number at most five. In particular, and equivalently, it holds if G is a complete k-partite graph and each part has at most five vertices.     

Independence number of products of Kneser graphs

We study the independence number of a product of Kneser graph $K(n,k)$ with itself, where we consider all four standard graph products. The cases of the direct, the lexicographic and the strong product of Kneser graphs are not difficult (the formula for $\alpha (K(n,k)⊠K(n,k))$ is presented in this paper), while the case of the Cartesian product of Kneser graphs is much more involved. We establish a lower bound and an upper bound for the independence number of $K(n,2)\square K(n,2)$, which are asymptotically tending to $n^3∕3$ and $3n^3∕8$, respectively. The former is obtained by a construction, which differs from the standard diagonalization procedure, while for the upper bound the $\ell$-independence number of Kneser graphs can be applied. We also establish some constructions in odd graphs $K(2k+1,k)$, which give a lower bound for the 2-independence number of these graphs, and prove that two such constructions give the same lower bound as a previously known one. Finally, we consider the $s$-stable Kneser graphs $K{(ks+1,k)}_{s-stab}$, derive a formula for their $\ell$-independence number, and give the exact value of the independence number of the Cartesian square of $K{(ks+1,k)}_{s-stab}$.     

Extremal perfect graphs for a bound on the domination number

We examine classes of extremal graphs for the inequality γ(G)?|V|-max{d(v)+β_v(G)}, where γ(G) is the domination number of graph G, d(v) is the degree of vertex v, and β_v(G) is the size of a largest matching in the subgraph of G induced by the non-neighbours of v. This inequality improves on the classical upper bound |V|-maxd(v) due to Claude Berge. We give a characterization of the bipartite graphs and of the chordal graphs that achieve equality in the inequality. The characterization implies that the extremal bipartite graphs can be recognized in polynomial time, while the corresponding problem remains NP-complete for the extremal chordal graphs.     

On graphs determining links with maximal number of components via medial construction

Let G be a connected plane graph, D(G) be the corresponding link diagram via medial construction, and μ(D(G)) be the number of components of the link diagram D(G). In this paper, we first provide an elementary proof that μ(D(G))≤n(G)+1, where n(G) is the nullity of G. Then we lay emphasis on the extremal graphs, i.e. the graphs with μ(D(G))=n(G)+1. An algorithm is given firstly to judge whether a graph is extremal or not, then we prove that all extremal graphs can be obtained from K₁ by applying two graph operations repeatedly. We also present a dual characterization of extremal graphs and finally we provide a simple criterion on structures of bridgeless extremal graphs.     

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.