Covering the edges of a graph by three odd subgraphs

We prove that any finite simple graph can be covered by three of its odd subgraphs, and we construct an infinite sequence of graphs where an edge‐disjoint covering by three odd subgraphs is not possible. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 77–82, 2006     

On maximum planar induced subgraphs

The nonplanar vertex deletion or vertex deletion vd(G) of a graph G is the smallest nonnegative integer k, such that the removal of k vertices from G produces a planar graph G^′. In this case G^′ is said to be a maximum planar induced subgraph of G. We solve a problem proposed by Yannakakis: find the threshold for the maximum degree of a graph G such that, given a graph G and a nonnegative integer k, to decide whether vd(G)?k is NP-complete. We prove that it is NP-complete to decide whether a maximum degree 3 graph G and a nonnegative integer k satisfy vd(G)?k. We prove that unless P=NP there is no polynomial-time approximation algorithm with fixed ratio to compute the size of a maximum planar induced subgraph for graphs in general. We prove that it is Max SNP-hard to compute vd(G) when restricted to a cubic input G. Finally, we exhibit a polynomial-time -approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph.     

Recognizing connectedness from vertex‐deleted subgraphs

Let G be a graph of order n. The vertex‐deleted subgraph G ? v, obtained from G by deleting the vertex v and all edges incident to v, is called a card of G. Let H be another graph of order n, disjoint from G. Then the number of common cards of G and H is the maximum number of disjoint pairs (v, w), where v and w are vertices of G and H, respectively, such that G ? v?H ? w. We prove that if G is connected and H is disconnected, then the number of common cards of G and H is at most ?n/2? + 1. Thus, we can recognize the connectedness of a graph from any ?n/2? + 2 of its cards. Moreover, we completely characterize those pairs of graphs that attain the upper bound and show that, with the exception of six pairs of graphs of order at most 7, any pair of graphs that attains the maximum is in one of four infinite families. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:285‐299, 2011     

Regular induced subgraphs of a random Graph

An old problem of Erd?s, Fajtlowicz, and Staton asks for the order of a largest induced regular subgraph that can be found in every graph on vertices. Motivated by this problem, we consider the order of such a subgraph in a typical graph on vertices, i.e., in a binomial random graph . We prove that with high probability a largest induced regular subgraph of has about vertices. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 235–250, 2011     

Forbidden induced subgraphs for star-free graphs

Let H be a family of connected graphs. A graph G is said to be H-free if G is H-free for every graph H in H. In Aldred et al. (2010) [1], it was pointed that there is a family of connected graphs H not containing any induced subgraph of the claw having the property that the set of H-free connected graphs containing a claw is finite, provided also that those graphs have minimum degree at least 2 and maximum degree at least 3. In the same work, it was also asked whether there are other families with the same property. In this paper, we answer this question by solving a wider problem. We consider not only claw-free graphs but the more general class of star-free graphs. Concretely, given t≥3, we characterize all the graph families H such that every large enough H-free connected graph is K_1,t-free. Additionally, for the case t=3, we show the families that one gets when adding the condition ∣H∣≤k for each positive integer k.     

Large induced subgraphs with equated maximum degree

For a graph G, denote by f_k(G) the smallest number of vertices that must be deleted from G so that the remaining induced subgraph has its maximum degree shared by at least k vertices. It is not difficult to prove that there are graphs for which already , where n is the number of vertices of G. It is conjectured that for every fixed k. We prove this for k=2,3. While the proof for the case k=2 is easy, already the proof for the case k=3 is considerably more difficult. The case k=4 remains open.A related parameter, s_k(G), denotes the maximum integer m so that there are k vertex-disjoint subgraphs of G, each with m vertices, and with the same maximum degree. We prove that for every fixed k, s_k(G)≥n/k−o(n). The proof relies on probabilistic arguments.     

Two forbidden induced subgraphs and well-quasi-ordering

It is known that a class of graphs defined by a single forbidden induced subgraph G is well-quasi-ordered by the induced subgraph relation if and only if G is an induced subgraph of P₄. However, very little is known about well-quasi-ordered classes of graphs defined by more than one forbidden induced subgraph. We conjecture that for any natural number k, there are finitely many minimal classes of graphs defined by k forbidden induced subgraphs which are not well-quasi-ordered by the induced subgraph relation and prove the conjecture for k=2. We explicitly reveal many of the minimal classes defined by two forbidden induced subgraphs which are not well-quasi-ordered and many of those which are well-quasi-ordered by the induced subgraph relation.     

Algebraic connectivity for vertex-deleted subgraphs, and a notion of vertex centrality

Let G be a connected graph, suppose that v is a vertex of G, and denote the subgraph formed from G by deleting vertex v by G?v. Denote the algebraic connectivities of G and G?v by α(G) and α(G?v), respectively. In this paper, we consider the functions ?(v)=α(G)−α(G?v) and , provide attainable upper and lower bounds on both functions, and characterise the equality cases in those bounds. The function κ yields a measure of vertex centrality, and we apply that measure to analyse certain graphs arising from food webs.     

Large induced subgraphs with three repeated degrees

For any positive integer k, let $C(k)$ denote the least integer such that any n-vertex graph has an induced subgraph with at least $n?C(k)$ vertices, in which at least $\min ?\{k,n?C(k)\}$ vertices are of the same degree. Caro, Shapira and Yuster initially studied this parameter and showed that $\mathrm{\Omega }(k\log ?k)\le C(k)\le {(8k)}^k$. For the first nontrivial case, the authors proved that $3\le C(3)\le 6$, and the exact value was left as an open problem. In this paper, we first show that $3\le C(3)\le 4$, improving the former result as well as a recent result of Kogan. For special families of graphs, we prove that $C(3)=3$ for $K_5$-free graphs, and $C(3)=1$ for large $C_{2s+1}$-free graphs. In addition, extending a result of Erd?s, Fajtlowicz and Staton, we assert that every $K_r$-free graph is an induced subgraph of a $K_r$-free graph in which no degree occurs more than three times.     

Average distance and maximum induced forest

With the help of the Graffiti system, Fajtlowicz conjectured around 1992 that the average distance between two vertices of a connected graph G is at most half the maximum order of an induced bipartite subgraph of G, denoted α₂(G). We prove a strengthening of this conjecture by showing that the average distance between two vertices of a connected graph G is at most half the maximum order of an induced forest, denoted F(G). Moreover, we characterize the graphs maximizing the average distance among all graphs G having a fixed number of vertices and a fixed value of F(G) or α₂(G). Finally, we conjecture that the average distance between two vertices of a connected graph is at most half the maximum order of an induced linear forest (where a linear forest is a union of paths). © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 31–54, 2009     

On covering graphs by complete bipartite subgraphs

We prove that, if a graph with e edges contains m vertex-disjoint edges, then m²/e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions.     

Characterizing path graphs by forbidden induced subgraphs

A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 369–384, 2009     

Two‐factors each component of which contains a specified vertex

It is shown that if G is a graph of order n with minimum degree δ(G), then for any set of k specified vertices {v₁,v₂,…,v_k} ? V(G), there is a 2‐factor of G with precisely k cycles {C₁,C₂,…,C_k} such that v_i ∈ V(C_i) for (1 ≤ i ≤ k) if or 3k + 1 ≤ n ≤ 4k, or 4k ≤ n ≤ 6k ? 3,δ(G) ≥ 3k ? 1 or n ≥ 6k ? 3, . Examples are described that indicate this result is sharp. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 188–198, 2003