Largest Non-Unique Subgraphs

The reduction number r(G) of a graph G is the maximum integer m≤|E(G)| such that the graphs G−E, E⊆E(G),|E|≤m, are mutually non-isomorphic, i.e., each graph is unique as a subgraph of G. We prove that and show by probabilistic methods that r(G) can come close to this bound for large orders. By direct construction, we exhibit graphs with large reduction number, although somewhat smaller than the upper bound. We also discuss similarities to a parameter introduced by Erdős and Rényi capturing the degree of asymmetry of a graph, and we consider graphs with few circuits in some detail. Supported by a grant from the Danish Natural Science Research Council.     

Counting Unbranched Subgraphs

Given an arbitrary finite graph, the polynomial associates a weight zcardF to each unbranched subgraph F of length cardF. We show that all the zeros of Q have negative real part.     

Subgraphs and well-quasi-ordering

Let ?? be a class of graphs and let ? be the subgraph or the induced subgraph relation. We call ? an ideal (with respect to ?) if ? implies that ?. In this paper, we study the ideals that are well-quasiordered by ?. The following are our main results. If ? is the subgraph relation, we characterize the well-quasi-ordered ideals in terms of exluding subgraphs. If?is the induced subgraph relation, we present three wellquasi-ordered ideals. We also construct examples to disprove some of the possible generalizations of our results. The connections between some of our results and digraphs are considered in this paper too.     

Subgraphs of colour-critical graphs

Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed. In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc _k n ² edges must be removed. In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph.     

Subgraphs of Random Match-Graphs

 A simple graph (match-graph) generated by two-cycles of a general model of a random digraph is considered. Based on relations between a special case of such a graph and a classical model of a random graph, some results about the existence and the number of subgraphs of a given type in a random match-graph are presented. Received: December 8, 1997 Final version received: September 16, 1999     

Bipartite Subgraphs and Quasi-Randomness

We say that a family of graphs is p-quasi-random, 0<p<1, if it shares typical properties of the random graph G(n,p); for a definition, see below. We denote by the class of all graphs H for which and the number of not necessarily induced labeled copies of H in G_n is at most (1+o(1))p^e(H)n^v(H) imply that is p-quasi-random. In this note, we show that all complete bipartite graphs K_a,b, a,b2, belong to for all 0<p<1.Acknowledgments We would like to thank Andrew Thomason for fruitful discussions and Yoshi Kohayakawa for organizing Extended Workshop on Combinatorics in eq5 Paulo, Ubatuba, and Rio de Janeiro, where a part of this work was done. We also thank the referees for their careful work.The first author was partially supported by NSF grant INT-0072064The second author was partially supported by NSF grants DMS-9970622, DMS-0301228 and INT-0072064Final version received: October 24, 2003     

Computing the girth of knots

We introduce a method to compute the girth of knots, defined by Hernndez and Lin, using the Jones and BrandtLickorishMillettHo polynomial. We determine the girth of all knots up to 10 crossings.     

On Subgraphs in Distance-Regular Graphs

Terwilliger [15] has given the diameter bound d (s – 1)(k – 1) + 1 for distance-regular graphs with girth 2s and valency k. We show that the only distance-regular graphs with even girth which reach this bound are the hypercubes and the doubled Odd graphs. Also we improve this bound for bipartite distance-regular graphs. Weichsel [17] conjectures that the only distance-regular subgraphs of a hypercube are the even polygons, the hypercubes and the doubled Odd graphs and proves this in the case of girth 4. We show that the only distance-regular subgraphs of a hypercube with girth 6 are the doubled Odd graphs. If the girth is equal to 8, then its valency is at most 12.     

Highly Symmetric Subgraphs of Hypercubes

Two questions are considered, namely (i) How many colors are needed for a coloring of the n-cube without monochromatic quadrangles or hexagons? We show that four colors suffice and thereby settle a problem of Erdös. (ii) Which vertex-transitive induced subgraphs does a hypercube have? An interesting graph has come up in this context: If we delete a Hamming code from the 7-cube, the resulting graph is 6-regular, vertex-transitive and its edges can be two-colored such that the two monochromatic subgraphs are isomorphic, cubic, edge-transitive, nonvertex-transitive graphs of girth 10.     

Online coloring graphs with high girth and high odd girth

We give an upper bound for the online chromatic number of graphs with high girth and for graphs with high odd girth generalizing Kierstead’s algorithm for graphs that contain neither a C₃ or C₅ as an induced subgraph.     

On 2-Detour Subgraphs of the Hypercube

A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V(G), d _H (x, y) ≤ d _G (x, y) + 2. We prove a conjecture of Erdős, Hamburger, Pippert, and Weakley by showing that for some positive constant c and every n, each 2-detour subgraph of the n-dimensional hypercube Q _n has at least clog₂ n · 2 ⁿ edges. József Balogh: Research supported in part by NSF grants DMS-0302804, DMS-0603769 and DMS-0600303, UIUC Campus Reseach Board #06139 and #07048, and OTKA 049398. Alexandr Kostochka: Research supported in part by NSF grants DMS-0400498 and DMS-0650784, and grant 06-01-00694 of the Russian Foundation for Basic Research.     

Circumference and girth

Let G be 2-connected graph with girth g and minimum degree d. Then each pair of vertices of G is joined by a path of length at least max{1/2(d ? 1)g, (d ? 3/2)(g ? 4) + 2} if g ? 4, and the length of a longest cycle of G is at least max{[(d ? 1)(g ? 2) + 2], [(2d ? 3)(g ? 4) + 4]}.     

The Evolution of Random Subgraphs of the Cube

be a random Qⁿ”-process, that is let Q₀ be the empty spanning subgraph of the cube Qⁿ and, for 1 ? t ? M = nN/2 = n2^n?1, let the graph Q_t be obtained from Q_t?1 by the random addition of an edge of Q_n not present in Q_t?1. When t is about N/2, a typical Q_t undergoes a certain “phase transition'': the component structure changes in a sudden and surprising way. Let t = (1 + ?) N/2 where ? is independent of n. Then all the components of a typical Q_t have o(N) vertices if ? < 0, while if ? > 0 then, as proved by Ajtai, Komlós, and Szemerédi, a typical Q_t has a “giant” component with at least α(?)N vertices, where α(?) > 0. In this note we give essentially best possible results concerning the emergence of this giant component close to the time of phase transition. Our results imply that if η > 0 is fixed and t ? (1 ? n^?η) N/2, then all components of a typical Q_t have at most n^β(η) vertices, where β(η) > 0. More importantly, if 60(log n)³/n ? ? = ?n = o(1), then the largest component of a typical Q_t has about 2?N vertices, while the second largest component has order O(n?^?2). Loosely put, the evolution of a typical Qⁿ process is such that shortly after time N/2 the appearance of each new edge results in the giant component acquiring 4 new vertices.     

Forbidden Induced Subgraphs for Toughness

Let be a family of connected graphs. A graph G is said to be ‐free if G is H‐free for every graph H in . We study the relation between forbidden subgraphs in a connected graph G and the resulting toughness of G. In particular, we consider the problem of characterizing the graph families such that every large enough connected ‐free graph is t‐tough. In this article, we solve this problem for every real positive number t. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 191–202, 2013     

Subgraphs of graphs, I

Let G and H be two simple graphs on p vertices. We give a sufficient condition, based on the minimum degree of the vertices of G and the maximum degree of the vertices of H, for H to be a subgraph of G.     

Ramsey-type Theorems with Forbidden Subgraphs

Dedicated to the memory of Paul Erdős   A graph is called H-free if it contains no induced copy of H. We discuss the following question raised by Erdős and Hajnal. Is it true that for every graph H, there exists an such that any H-free graph with n vertices contains either a complete or an empty subgraph of size at least ? We answer this question in the affirmative for a special class of graphs, and give an equivalent reformulation for tournaments. In order to prove the equivalence, we establish several Ramsey type results for tournaments. Received August 22, 1999 RID="*" ID="*" Supported by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. RID="†" ID="†" Supported by NSF grant CR-9732101, PSC-CUNY Research Award 663472, and OTKA-T-020914. RID="‡" ID="‡" Supported by TKI grant Stochastics@TUB, and OTKA-T-026203.