Graphs with Least Eigenvalue −2: The Star Complement Technique

Let G be a connected graph with least eigenvalue –2, of multiplicity k. A star complement for –2 in G is an induced subgraph H = G – X such that |X| = k and –2 is not an eigenvalue of H. In the case that G is a generalized line graph, a characterization of such subgraphs is used to decribe the eigenspace of –2. In some instances, G itself can be characterized by a star complement. If G is not a generalized line graph, G is an exceptional graph, and in this case it is shown how a star complement can be used to construct G without recourse to root systems.     

On eigenvalue multiplicity and the girth of a graph

Suppose that G is a connected graph of order n and girth g<n. Let k be the multiplicity of an eigenvalue μ of G. Sharp upper bounds for k are n-g+2 when μ∈{-1,0}, and n-g otherwise. The graphs attaining these bounds are described.     

Relations between (κ, τ)-regular sets and star complements

Let G be a finite graph with an eigenvalue µ of multiplicity m. A set X of m vertices in G is called a star set for µ in G if µ is not an eigenvalue of the star complement G\X which is the subgraph of G induced by vertices not in X. A vertex subset of a graph is (κ, τ)-regular if it induces a κ-regular subgraph and every vertex not in the subset has τ neighbors in it. We investigate the graphs having a (κ, τ)-regular set which induces a star complement for some eigenvalue. A survey of known results is provided and new properties for these graphs are deduced. Several particular graphs where these properties stand out are presented as examples.     

Edge fault tolerance analysis of super k-restricted connected networks

An edge cut X of a connected graph G is a k-restricted edge cut if G-X is disconnected and every component of G-X has at least k vertices. Additionally, if the deletion of a minimum k-restricted edge cut isolates a connected component of k vertices, then the graph is said to be super-λ_k. In this paper, several sufficient conditions yielding super-λ_k graphs are given in terms of the girth and the diameter.     

Graphs admitting transitive commutative group actions

Let X be a compact metric space, and Homeo(X) be the group consisting of all homeomorphisms from X to X. A subgroup H of Homeo(X) is said to be transitive if there exists a point x∈X such that {k(x):k∈H} is dense in X. In this paper we show that, if X=G is a connected graph, then the following five conditions are equivalent: (1) Homeo(G) has a transitive commutative subgroup; (2) G admits a transitive Z²-action; (3) G admits an edge-transitive commutative group action; (4) G admits an edge-transitive Z²-action; (5) G is a circle, or a k-fold loop with k?2, or a k-fold polygon with k?2, or a k-fold complete bigraph with k?1. As a corollary of this result, we show that a finite connected simple graph whose automorphism group contains an edge-transitive commutative subgroup is either a cycle or a complete bigraph.     

Mader’s Conjecture On Extremely Critical Graphs

A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K_2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism). Here we prove this conjecture.     

Co-cliques and star complements in extremal strongly regular graphs

Suppose that the positive integer μ is the eigenvalue of largest multiplicity in an extremal strongly regular graph G. By interlacing, the independence number of G is at most 4μ² + 4μ − 2. Star complements are used to show that if this bound is attained then either (a) μ = 1 and G is the Schläfli graph or (b) μ = 2 and G is the McLaughlin graph.     

On (s,t)-supereulerian graphs in locally highly connected graphs

Given two nonnegative integers s and t, a graph G is (s,t)-supereulerian if for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y|≤t, there is a spanning eulerian subgraph H of G that contains X and avoids Y. We prove that if G is connected and locally k-edge-connected, then G is (s,t)-supereulerian, for any pair of nonnegative integers s and t with s+t≤k−1. We further show that if s+t≤k and G is a connected, locally k-edge-connected graph, then for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y≤t, there is a spanning eulerian subgraph H that contains X and avoids Y, if and only if G−Y is not contractible to K₂ or to K_2,l with l odd.     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

Packing edge-disjoint cycles in graphs and the cyclomatic number

For a graph G let μ(G) denote the cyclomatic number and let ν(G) denote the maximum number of edge-disjoint cycles of G.We prove that for every k≥0 there is a finite set P(k) such that every 2-connected graph G for which μ(G)−ν(G)=k arises by applying a simple extension rule to a graph in P(k). Furthermore, we determine P(k) for k≤2 exactly.     

A characterization of maximal non-k-factor-critical graphs

A graph G of order p is k-factor-critical,where p and k are positive integers with the same parity, if the deletion of any set of k vertices results in a graph with a perfect matching. G is called maximal non-k-factor-critical if G is not k-factor-critical but G+e is k-factor-critical for every missing edge e∉E(G). A connected graph G with a perfect matching on 2n vertices is k-extendable, for 1?k?n-1, if for every matching M of size k in G there is a perfect matching in G containing all edges of M. G is called maximal non-k-extendable if G is not k-extendable but G+e is k-extendable for every missing edge e∉E(G) . A connected bipartite graph G with a bipartitioning set (X,Y) such that |X|=|Y|=n is maximal non-k-extendable bipartite if G is not k-extendable but G+xy is k-extendable for any edge xy∉E(G) with x∈X and y∈Y. A complete characterization of maximal non-k-factor-critical graphs, maximal non-k-extendable graphs and maximal non-k-extendable bipartite graphs is given.     

On graphs whose star sets are (co-)cliques

In this paper we study graphs all of whose star sets induce cliques or co-cliques. We show that the star sets of every tree for each eigenvalue are independent sets. Among other results it is shown that each star set of a connected graph G with three distinct eigenvalues induces a clique if and only if G=K_1,2 or K_2,…,2. It is also proved that stars are the only graphs with three distinct eigenvalues having a star partition with independent star sets.     

Toughness and the existence of fractional k-factors of graphs

The toughness of a graph G, t(G), is defined as t(G)=min{|S|/ω(G-S)|S⊆V(G),ω(G-S)>1} where ω(G-S) denotes the number of components of G-S or t(G)=+∞ if G is a complete graph. Much work has been contributed to the relations between toughness and the existence of factors of a graph. In this paper, we consider the relationship between the toughness and the existence of fractional k-factors. It is proved that a graph G has a fractional 1-factor if t(G)?1 and has a fractional k-factor if t(G)?k-1/k where k?2. Furthermore, we show that both results are best possible in some sense.     

Cliques, minors and apex graphs

In this paper, we proved the following result: Let G be a (k+2)-connected, non-(k−3)-apex graph where k≥2. If G contains three k-cliques, say L₁, L₂, L₃, such that |L_i∩L_j|≤k−2(1≤i<j≤3), then G contains a K_k+2 as a minor. Note that a graph G is t-apex if G−X is planar for some subset X⊆V(G) of order at most t.This theorem generalizes some earlier results by Robertson, Seymour and Thomas [N. Robertson, P.D. Seymour, R. Thomas, Hadwiger conjecture for K₆-free graphs, Combinatorica 13 (1993) 279-361.], Kawarabayashi and Toft [K. Kawarabayashi, B. Toft, Any 7-chromatic graph has K₇ or K_4,4 as a minor, Combinatorica 25 (2005) 327-353] and Kawarabayashi, Luo, Niu and Zhang [K. Kawarabayashi, R. Luo, J. Niu, C.-Q. Zhang, On structure of k-connected graphs without K_k-minor, Europ. J. Combinatorics 26 (2005) 293-308].     

Spectral upper bounds for the order of a k-regular induced subgraph

Let G be a simple graph with least eigenvalue λ and let S be a set of vertices in G which induce a subgraph with mean degree k. We use a quadratic programming technique in conjunction with the main angles of G to establish an upper bound of the form |S|?inf{(k+t)q_G(t):t>-λ} where q_G is a rational function determined by the spectra of G and its complement. In the case k=0 we obtain improved bounds for the independence number of various benchmark graphs.     

On minimally circular-imperfect graphs

A circular-perfect graph is a graph of which each induced subgraph has the same circular chromatic number as its circular clique number. In this paper, (1) we prove a lower bound on the order of minimally circular-imperfect graphs, and characterize those that attain the bound; (2) we prove that if G is a claw-free minimally circular-imperfect graph such that ω_c(G-x)>ω(G-x) for some x∈V(G), then G=K_(2k+1)/2+x for an integer k; and (3) we also characterize all minimally circular-imperfect line graphs.     

3-Factor-criticality in domination critical graphs

A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k-1 vertices. The structure of k-γ-critical graphs remains far from completely understood when k?3.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G) and is bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G). More generally, a graph is said to be k-factor-critical if G-S has a perfect matching for every set S of k vertices in G. In three previous papers [N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs, Discrete Math. 272 (2003) 5-15; N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs. II. Utilitas Math. 70 (2006) 11-32], we explored the toughness of 3-γ-critical graphs and some of their matching properties. In particular, we obtained some properties which are sufficient for a 3-γ-critical graph to be factor-critical and, respectively, bicritical. In the present work, we obtain similar results for k-factor-critical graphs when k=3.     

Generating all subsets of a finite set with disjoint unions

If X is an n-element set, we call a family G⊂PX a k-generator for X if every x⊂X can be expressed as a union of at most k disjoint sets in G. Frein, Lévêque and Seb? conjectured that for n>2k, the smallest k-generators for X are obtained by taking a partition of X into classes of sizes as equal as possible, and taking the union of the power-sets of the classes. We prove this conjecture for all sufficiently large n when k=2, and for n a sufficiently large multiple of k when k?3.     

On 3-Steiner simplicial orderings

Let G be a connected graph and S a nonempty set of vertices of G. A Steiner tree for S is a connected subgraph of G containing S that has a minimum number of edges. The Steiner interval for S is the collection of all vertices in G that belong to some Steiner tree for S. Let k≥2 be an integer. A set X of vertices of G is k-Steiner convex if it contains the Steiner interval of every set of k vertices in X. A vertex x∈X is an extreme vertex of X if X?{x} is also k-Steiner convex. We call such vertices k-Steiner simplicial vertices. We characterize vertices that are 3-Steiner simplicial and give characterizations of two classes of graphs, namely the class of graphs for which every ordering produced by Lexicographic Breadth First Search is a 3-Steiner simplicial ordering and the class for which every ordering of every induced subgraph produced by Maximum Cardinality Search is a 3-Steiner simplicial ordering.     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001