Structure of independent sets in direct products of some vertex-transitive graphs

Let Circ( r, n) be a circular graph. It is well known that its independence number α(Circ(r, n)) = r. In this paper we prove that α(Circ(r, n) × H ) = max{r|H |, nα(H )} for every vertex transitive graph H, and describe the structure of maximum independent sets in Circ(r, n) × H. As consequences, we prove α(G × H ) = max{α(G)|V (H )|, α(H )|V (G)|} for G being Kneser graphs, and the graphs defined by permutations and partial permutations, respectively. The structure of maximum independent sets in these direct products is also described.     

Independent sets of maximal size in tensor powers of vertex‐transitive graphs

Let G be a connected, nonbipartite vertex‐transitive graph. We prove that if the only independent sets of maximal cardinality in the tensor product G × G are the preimages of the independent sets of maximal cardinality in G under projections, then the same holds for all finite tensor powers of G, thus providing an affirmative answer to a question raised by Larose and Tardif (J Graph Theory 40(3) (2002), 162–171). © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 295‐301, 2009     

Large families of mutually embeddable vertex‐transitive graphs

For each infinite cardinal κ, we give examples of 2^κ many non‐isomorphic vertex‐transitive graphs of order κ that are pairwise isomorphic to induced subgraphs of each other. We consider examples of graphs with these properties that are also universal, in the sense that they embed all graphs with smaller orders as induced subgraphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 99–106, 2003     

Polar graphs and maximal independent sets

We study two central problems of algorithmic graph theory: finding maximum and minimum maximal independent sets. Both problems are known to be NP-hard in general. Moreover, they remain NP-hard in many special classes of graphs. For instance, the problem of finding minimum maximal independent sets has been recently proven to be NP-hard in the class of so-called (1,2)-polar graphs. On the other hand, both problems can be solved in polynomial time for (1,1)-polar, also known as split graphs. In this paper, we address the question of distinguishing new classes of graphs admitting polynomial-time solutions for the two problems in question. To this end, we extend the hierarchy of (α,β)-polar graphs and study the computational complexity of the problems on polar graphs of special types.     

Projectivity and independent sets in powers of graphs

We investigate the relationship between projectivity and the structure of maximal independent sets in powers of circular graphs, Kneser graphs and truncated simplices. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 162–171, 2002     

Tutte sets in graphs I: Maximal tutte sets and D‐graphs

A well‐known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency of G. A subset X of V(G) for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. In this article, we study the structural aspects of maximal Tutte sets in a graph G. Towards this end, we introduce a related graph D(G). We first show that the maximal Tutte sets in G are precisely the maximal independent sets in its D‐graph D(G), and then continue with the study of D‐graphs in their own right, and of iterated D‐graphs. We show that G is isomorphic to a spanning subgraph of D(G), and characterize the graphs for which G?D(G) and for which D(G)?D²(G). Surprisingly, it turns out that for every graph G with a perfect matching, D³(G)?D²(G). Finally, we characterize bipartite D‐graphs and comment on the problem of characterizing D‐graphs in general. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 343–358, 2007     

On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

On independent sets in random graphs

The independence number of a sparse random graph G(n,m) of average degree d = 2m/n is well‐known to be with high probability, with in the limit of large d. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size , i.e., about half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with size for any fixed (independent of both d and n). In this paper we prove that the combinatorial structure of the independent set problem in random graphs undergoes a phase transition as the size k of the independent sets passes the point . Roughly speaking, we prove that independent sets of size form an intricately rugged landscape, in which local search algorithms seem to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independent sets. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 436–486, 2015     

Tetravalent vertex‐transitive graphs of order 4p

A graph is vertex‐transitive if its automorphism group acts transitively on vertices of the graph. A vertex‐transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this article, the tetravalent vertex‐transitive non‐Cayley graphs of order 4p are classified for each prime p. As a result, there are one sporadic and five infinite families of such graphs, of which the sporadic one has order 20, and one infinite family exists for every prime p>3, two families exist if and only if p≡1 (mod 8) and the other two families exist if and only if p≡1 (mod 4). For each family there is a unique graph for a given order. © 2011 Wiley Periodicals, Inc.     

Cubic vertex‐transitive graphs of order 2pq

A graph is vertex?transitive or symmetric if its automorphism group acts transitively on vertices or ordered adjacent pairs of vertices of the graph, respectively. Let G be a finite group and S a subset of G such that 1?S and S={s^?1 | s∈S}. The Cayleygraph Cay(G, S) on G with respect to S is defined as the graph with vertex set G and edge set {{g, sg} | g∈G, s∈S}. Feng and Kwak [J Combin Theory B 97 (2007), 627–646; J Austral Math Soc 81 (2006), 153–164] classified all cubic symmetric graphs of order 4p or 2p² and in this article we classify all cubic symmetric graphs of order 2pq, where p and q are distinct odd primes. Furthermore, a classification of all cubic vertex‐transitive non‐Cayley graphs of order 2pq, which were investigated extensively in the literature, is given. As a result, among others, a classification of cubic vertex‐transitive graphs of order 2pq can be deduced. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 285–302, 2010     

Constructing cubic edge‐ but not vertex‐transitive graphs

An infinite family of cubic edge‐transitive but not vertex‐transitive graphs with edge stabilizer isomorphic to ℤ₂ is constructed. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 152–160, 2000     

Maximal independent sets in graphs with at most r cycles

We find the maximum number of maximal independent sets in two families of graphs. The first family consists of all graphs with n vertices and at most r cycles. The second family is all graphs of the first family which are connected and satisfy n ≥ 3r. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 270–282, 2006     

Large Cayley graphs and vertex‐transitive non‐Cayley graphs of given degree and diameter

For any d?5 and k?3 we construct a family of Cayley graphs of degree d, diameter k, and order at least k((d?3)/3)^k. By comparison with other available results in this area we show that our family gives the largest currently known Cayley graphs for a wide range of sufficiently large degrees and diameters. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 87–98, 2010     

Estimates of the number of independent sets in graphs with a fixed independence number

Attainable estimates of the number of independent sets in graphs with a given size of the maximal independent set are obtained. Three graph classes—trees, forests, and the class of all graphs—are considered. Extremal graphs are described.     

An infinite series of regular edge‐ but not vertex‐transitive graphs

Let n be an integer and q be a prime power. Then for any 3 ≤ n ≤ q?1, or n=2 and q odd, we construct a connected q‐regular edge‐but not vertex‐transitive graph of order 2qⁿ⁺¹. This graph is defined via a system of equations over the finite field of q elements. For n=2 and q=3, our graph is isomorphic to the Gray graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 249–258, 2002     

Maximal and maximum independent sets in graphs with at most r cycles

Let m(G) denote the number of maximal independent sets of vertices in a graph G and let c(n,r) be the maximum value of m(G) over all connected graphs with n vertices and at most r cycles. A theorem of Griggs, Grinstead, and Guichard gives a formula for c(n,r) when r is large relative to n, while a theorem of Goh, Koh, Sagan, and Vatter does the same when r is small relative to n. We complete the determination of c(n,r) for all n and r and characterize the extremal graphs. Problems for maximum independent sets are also completely resolved. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 283–314, 2006     

NEIGHBORHOOD UNION OF INDEPENDENT SETS AND HAMILTONICITY OF CLAW-FREE GRAPHS

Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u. For any U V(G) ,let N(U)=Uu,∈UN(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K1.3. One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al. : Let G be a 2-connected claw-free graph of order n,and d(u) d(v) d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that, for any three positive integers s ,t and w,such that if G is a (s t w-1)connected claw-free graph of order n,and d(S) d(T) d(W)＞n-(s t w) for every three disjoint independent vertex sets S,T,W with |S |=s, |T|=t, |W|=w,and S∪T∪W is also independent ,then G is Hamiltonian. Other related results are obtained too.     

Another note on cliques and independent sets

Entringer, Goddard, and Henning studied graphs in which every vertex belongs to both an (m + 1)‐clique and an independent (n + 1)‐set; they proved that there is such a graph of order p if and only if . We give an alternative and slightly easier proof of this fact, relating it to combinatorial matrix theory. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 173–175, 2000     

Maximum independent sets in 3- and 4-regular Hamiltonian graphs

Smooth 4-regular Hamiltonian graphs are generalizations of cycle-plus-triangles graphs. While the latter have been shown to be 3-choosable, 3-colorability of the former is NP-complete. In this paper we first show that the independent set problem for 3-regular Hamiltonian planar graphs is NP-complete, and using this result we show that this problem is also NP-complete for smooth 4-regular Hamiltonian graphs. We also show that this problem remains NP-complete if we restrict the problem to the existence of large independent sets (i.e., independent sets whose size is at least one third of the order of the graphs).     

Two problems on independent sets in graphs

Let i_t(G) denote the number of independent sets of size t in a graph G. Levit and Mandrescu have conjectured that for all bipartite G the sequence (i_t(G))_t≥0 (the independent set sequence of G) is unimodal. We provide evidence for this conjecture by showing that this is true for almost all equibipartite graphs. Specifically, we consider the random equibipartite graph G(n,n,p), and show that for any fixed p∈(0,1] its independent set sequence is almost surely unimodal, and moreover almost surely log-concave except perhaps for a vanishingly small initial segment of the sequence. We obtain similar results for .We also consider the problem of estimating i(G)=∑_t≥0i_t(G) for G in various families. We give a sharp upper bound on the number of independent sets in an n-vertex graph with minimum degree δ, for all fixed δ and sufficiently large n. Specifically, we show that the maximum is achieved uniquely by K_δ,n−δ, the complete bipartite graph with δ vertices in one partition class and n−δ in the other.We also present a weighted generalization: for all fixed x>0 and δ>0, as long as n=n(x,δ) is large enough, if G is a graph on n vertices with minimum degree δ then ∑_t≥0i_t(G)x^t≤∑_t≥0i_t(K_δ,n−δ)x^t with equality if and only if G=K_δ,n−δ.