Geodesic subgraphs

Define a geodesic subgraph of a graph to be a subgraph H with the property that any geodesic of two points of H is in H. The trivial geodesic subgraphs are the complete graphs K_n' n ≧ 0, and G itself. We characterize all (finite, simple, connected) graphs with only the trivial geodesic subgraphs, and give an algorithm for their construction. We do this also for triangle-free graphs.     

Bipartite subgraphs

It is shown that there exists a positivec so that for any large integerm, any graph with 2m ²edges contains a bipartite subgraph with at least edges. This is tight up to the constantc and settles a problem of Erdös. It is also proved that any triangle-free graph withe>1 edges contains a bipartite subgraph with at least e/2+c e ^4/5 edges for some absolute positive constantc. This is tight up to the constantc.Research supported in part by a USA Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.     

Distance-residual subgraphs

For a connected finite graph G and a subset V₀ of its vertex set, a distance-residual subgraph is a subgraph induced on the set of vertices at the maximal distance from V₀. Some properties and examples of distance-residual subgraphs of vertex-transitive, edge-transitive, bipartite and semisymmetric graphs are presented. The relations between the distance-residual subgraphs of product graphs and their factors are explored.     

Multiplicities of subgraphs

A former conjecture of Burr and Rosta [1], extending a conjecture of Erds [2], asserted that in any two-colouring of the edges of a large complete graph, the proportion of subgraphs isomorphic to a fixed graphG which are monochromatic is at least the proportion found in a random colouring. It is now known that the conjecture fails for some graphsG, includingG=K _p forp4.We investigate for which graphsG the conjecture holds. Our main result is that the conjecture fails ifG containsK ₄ as a subgraph, and in particular it fails for almost all graphs.     

Degree constrained subgraphs

In this paper, we present new structural results about the existence of a subgraph where the degrees of the vertices are pre-specified. Further, we use these results to prove a 16-edge-weighting version of a conjecture by Karoński, ?uczak and Thomason, an asymptotic 2-edge-weighting version of the same conjecture, and a version of Louigi's Conjecture.     

Maximum k-colorable subgraphs

A lower bound is established on the number of edges in a maximum k-colorable subgraph of a loopless graph G. For the special case of 3-regular graphs, lower bounds are also determined on the maximum number of edges in a bipartite subgraph whose color classes are of equal size.     

Maximal chordal subgraphs

An algorithm for finding maximal chordal subgraphs is developed that has worst-case time complexity of O(|E|Δ), where |E| is the number of edges in G and Δ is the maximum vertex degree in G. The study of maximal chordal subgraphs is motivated by their usefulness as computationally efficient structures with which to approximate a general graph. Two examples are given that illustrate potential applications of maximal chordal subgraphs. One provides an alternative formulation to the maximum independent set problem on a graph. The other involves a novel splitting scheme for solving large sparse systems of linear equations.     

Detecting induced subgraphs

An s-graph is a graph with two kinds of edges: subdivisible edges and real edges. A realisation of an s-graph B is any graph obtained by subdividing subdivisible edges of B into paths of arbitrary length (at least one). Given an s-graph B, we study the decision problem Π_B whose instance is a graph G and question is “Does G contain a realisation of B as an induced subgraph?”. For several B’s, the complexity of Π_B is known and here we give the complexity for several more.Our NP-completeness proofs for Π_B’s rely on the NP-completeness proof of the following problem. Let be a set of graphs and d be an integer. Let be the problem whose instance is (G,x,y) where G is a graph whose maximum degree is at most d, with no induced subgraph in and x,yV(G) are two non-adjacent vertices of degree 2. The question is “Does G contain an induced cycle passing through x,y?”. Among several results, we prove that is NP-complete. We give a simple criterion on a connected graph H to decide whether is polynomial or NP-complete. The polynomial cases rely on the algorithm three-in-a-tree, due to Chudnovsky and Seymour.     

Distance-preserving subgraphs of hypercubes

We give a characterization of connected subgraphs G of hypercubes H such that the distance in G between any two vertices a, b?G is the same as their distance in H. The hypercubes are graphs which generalize the ordinary cube graph.     

Hexagon-free subgraphs of hypercubes

It is shown (for all n ≥ 3) that the edges of the n-cube can be 3-colored in such a way that there is no monochromatic 4-cycle or 6-cycle. © 1993 John Wiley & Sons, Inc.     

Induced subgraphs of hypercubes

Let _Qk$Q_k$ denote the k$k$-dimensional hypercube on 2^k$2^k$ vertices. A vertex in a subgraph of _Qk$Q_k$ is full   if its degree is k$k$. We apply the Kruskal–Katona Theorem to compute the maximum number of full vertices an induced subgraph on n≤2^k$n\le 2^k$ vertices of _Qk$Q_k$ can have, as a function of k$k$ and n$n$. This is then used to determine min(max(|V(_H1)|,|V(_H2)|))$min(max(\left|V\left(H_1\right)\right|,\left|V\left(H_2\right)\right|))$ where (i) _H1$H_1$ and _H2$H_2$ are induced subgraphs of _Qk$Q_k$, and (ii) together they cover all the edges of _Qk$Q_k$, that is E(_H1)∪E(_H2)=E(_Qk)$E\left(H_1\right)\cup E\left(H_2\right)=E\left(Q_k\right)$.     

Complete subgraphs are elusive

We would like to decide whether a graph with a given vertex set has a certain property. We do this by probing the pairs of vertices one by one, i.e., asking whether a given pair of vertices is an edge or not. At each stage we make full use of the information we have up to that point. If there is an algorithm (a sequence of probes depending on the previous information) that allows us to come to a decision before checking every pair, the property is said to be incomplete, otherwise it is called complete or elusive. We show that the property of containing a complete subgraph with a given number of vertices is elusive. The proof also implies that the property of being r-chromatic (r fixed) is elusive.     

Induced subgraphs and well-quasi-ordering

We study classes of finite, simple, undirected graphs that are (1) lower ideals (or hereditary) in the partial order of graphs by the induced subgraph relation ≤_i, and (2) well-quasi-ordered (WQO) by this relation. The main result shows that the class of cographs (P₄-free graphs) is WQO by ≤_i, and that this is the unique maximal lower ideal with one forbidden subgraph that is WQO. This is a consequence of the famous Kruskal theorem. Modifying our idea we can prove that P₄-reducible graphs build a WQO class. Other examples of lower ideals WQO by ≤_i are also given.     

Large induced degenerate subgraphs

A graphH isd-degenerate if every subgraph of it contains a vertex of degree smaller thand. For a graphG, let _d (G) denote the maximum number of vertices of an inducedd-degenerate subgraph ofG. Sharp lowers bounds for _d (G) in terms of the degree sequence ofG are obtained, and the minimum number of edges of a graphG withn vertices and ₂ (G) m is determined precisely for allm n. Research supported in part by an Allon Fellowship and by a Bat-Sheva de Rothschild grant.Research supported in part by NSF grant MCS 8301867, and by a Sloan Research Fellowship.