Independence numbers of random subgraphs of distance graphs

We consider the distance graph G(n, r, s), whose vertices can be identified with r-element subsets of the set {1, 2,..., n}, two arbitrary vertices being joined by an edge if and only if the cardinality of the intersection of the corresponding subsets is s. For s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erd?s–Ko–Rado problem and also play an important role in combinatorial geometry and coding theory. We study some properties of random subgraphs of G(n, r, s) in the Erd?s–Rényi model, in which every edge occurs in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, r, s) for the case of constant r and s. The independence number of a random subgraph is Θ(log₂n) times as large as that of the graph G(n, r, s) itself for r ≤ 2s + 1, while for r > 2s + 1 one has asymptotic stability: the two independence numbers asymptotically coincide.     

On the number of edges in induced subgraphs of a special distance graph

We obtain new estimates for the number of edges in induced subgraphs of a special distance graph.     

Packing subgraphs in a graph

We show that the problem of packing edges and triangles in a graph in order to cover the maximum number of nodes can be solved in polynomial time. More generally we present results for the problem of packing edges and a family of hypomatchable subgraphs.     

A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph

We consider non-overlapping subgraphs of fixed order in the random graph K_n, p(n). Fix a strictly strongly balanced graph G. A subgraph of K_{n, p(n)} isomorphic to G is called a G-subgraph. Let X_n be the number of G-subgraphs of K_{n, p(n)} vertex disjoint to all other G-subgraphs. We show that if E[X_n]→∞ as n→, then X_n/E[X_n] converges to 1 in probability. Also, if E[X_n]→c as n→∞, then X_n satisfies a Poisson limit theorem. the Poisson limit theorem is shown using a correlation inequality similar to those appeared in Janson, ?uczak, and Ruciñski[8] and Boppana and Spencer [4].     

The ratio of the distance irredundance and domination numbers of a graph

Let n ≥ 1 be an integer and let G be a graph. A set D of vertices in G is defined to be an n-dominating set of G if every vertex of G is within distance n from some vertex of D. The minimum cardinality among all n-dominating sets of G is called the n-domination number of G and is denoted by γ_n(G). A set / of vertices in G is n-irredundant if for every vertex x ∈ / there exists a vertex y that is within distance n from x but at distance greater than n from every vertex of / - {x}. The n-irredundance number of G, denoted by ir_n(G), is the minimum cardinality taken over all maximal n-irredundant sets of vertices of G. We show that inf{ir_n(G)/γ_n(G) | G is an arbitrary finite undirected graph with neither loops nor multiple edges} = 1/2 with the infimum not being attained. Subsequently, we show that 2/3 is a lower bound on all quotients ir_n(T)/γ_n(T) in which T is a tree. Furthermore, we show that, for n ≥ 2, this bound is sharp. These results extend those of R. B. Allan and R.C. Laskar [“On Domination and Some Related Concepts in Graph Theory,” Utilitas Mathematica, Vol. 21 (1978), pp. 43–56], B. Bollobás and E. J. Cockayne [“Graph-Theoretic Parameters Concerning Domination, Independence and Irredundance,” Journal of Graph Theory, Vol. 3 (1979), pp. 241–249], and P. Damaschke [Irredundance Number versus Domination Number, Discrete Mathematics, Vol. 89 (1991), pp. 101–104].     

Covering a graph by topological complete subgraphs

Every graph onn vertices can be covered byex(n, TK ₄ ) =2n – 3 TK ₄ -subgraphs and edges. A similar result might hold for arbitrary topological (complete) subgraphs as indicated by the following result: Every graph onn vertices can be covered by 65ex(n, TK _p )TK _p -subgraphs and edges. IfH is a connected graph (|H| 3) then every graph onn vertices can be covered by 400ex(n, TH) TH-subgraphs and edges. Similar questions for coverings by odd and even cycles are also considered.This author's work was done while he was a guest at the Hungarian Academy of Sciences.     

On the probability of the occurrence of a copy of a fixed graph in a random distance graph

The threshold probability of the occurrence of a copy of a balanced graph in a random distance graph is obtained. The technique used by P. Erd?s and A. Rényi for determining the threshold probability for the classical random graph could not be applied in the model under consideration. In this connection, a new method for deriving estimates of the number of copies of a balanced graph in a complete distance graph is developed.     

Crossing-critical edges and Kuratowski subgraphs of a graph

An edge e of a graph G is said to be crossing-critical if cr(G ? e) < cr(G), where cr(G) denotes the crossing number of G on the plane. It is proved that any crossing-critical edge e of a graph G for which cr(G ? e) ≤ 1 belongs to a subdivision of K₅ or K_{3, 3}, the Kuratowski subgraphs of G. Further, as regards crossing-critical edges e of G for which cr(G ? e) ≥ 5, it is shown that the properties of “being a crossing-critical edge of G” and “being contained in a Kuratowski subgraph of G” are independent.     

On a class of isometric subgraphs of a graph

In a graphG, which has a loop at every vertex, a connected subgraphH=(V(H),E(H)) is a retract if, for anya, b ∈V(H) and for any pathsP, Q inG, both joininga tob, and satisfying |Q|≧ ≧|P|, thenP ⫅V(H) wheneverQ ⫅V(H). As such subgraphs can be described by a closure operator we are led to the investigation of the corresponding complete lattice of “closed” subgraphs. For example, in this complete lattice every element is the infimum of an irredundant family of infimum irreducible elements. The work presented here was supported in part by N.S.E.R.C. Operating Grant No. A4077.     

Distance-regular subgraphs in a distance-regular graph, II

Let Γ be a distance-regular graph with r = l(1, a₁, b₁), a₁ > 0 and c_2r+1 = 1. We show the existence of a collinearity graph of a Moore geometry of diameter r + 1 as a subgraph in Γ. In particular, we show that r = 1.     

On the number of homogeneous subgraphs of a graph

Let us defineG(n) to be the maximum numberm such that every graph onn vertices contains at leastm homogeneous (i.e. complete or independent) subgraphs. Our main result is exp (0.7214 log² n) ≧G(n) ≧ exp (0.2275 log² n), the main tool is a Ramsey—Turán type theorem. We formulate a conjecture what supports Thomason’s conjecture R(k, k)^1/k = 2.     

On certain subgraphs of a complete transitively directed graph

Let G_n be a complete transitively directed graph with n + 1 vertices v₀, v₁, …, v_n. Let ψ(n) be the number of subgraphs H of G_n where each vertex in H lies along a directed path from v₀ to v_n in H. ψ(n) and some related quantities are calculated.     

Spanning subgraphs of random graphs

We propose a problem concerning the determination of the threshold function for the edge probability that guarantees, almost surely, the existence of various sparse spanning subgraphs in random graphs. We prove some bounds and demonstrate them in the cases of ad-cube and a two dimensional lattice.     

Independence and graph homomorphisms graph homomorphisms

A graph with n vertices that contains no triangle and no 5-cycle and minimum degree exceeding n/4 contains an independent set with at least (3n)/7 vertices. This is best possible. The proof proceeds by producing a homomorphism to the 7-cycle and invoking the No Homomorphism Lemma. For k ≥ 4, a graph with n vertices, odd girth 2k+1, and minimum degree exceeding n/(k+1) contains an independent set with at least kn/(2k+1) vertices; however, we suspect this is not best possible. © 1993 John Wiley & Sons, Inc.     

Extremal subgraphs of random graphs

We shall prove that if L is a 3-chromatic (so called “forbidden”) graph, and —Rⁿ is a random graph on n vertices, whose edges are chosen independently, with probability p, and —Bⁿ is a bipartite subgraph of Rⁿ of maximum size, —Fⁿ is an L-free subgraph of Rⁿ of maximum size, then (in some sense) Fⁿ and Bⁿ are very near to each other: almost surely they have almost the same number of edges, and one can delete O_p(1) edges from Fⁿ to obtain a bipartite graph. Moreover, with p = 1/2 and L any odd cycle, Fⁿ is almost surely bipartite.     

On the existence of two non-neighboring subgraphs in a graph

Does there exist a functionf(r, n) such that each graphG with _Z (G)≧f(r, n) contains either a complete subgraph of orderr or else two non-neighboringn-chromatic subgraphs? It is known thatf(r, 2) exists and we establish the existence off(r, 3). We also give some interesting results about graphs which do not contain two independent edges.