There Are No Non-Trivially Uniformly (t, r)-Regular Graphs for t > 2.

Dean Hoffman^{1}, Peter Johnson^{1}, Kevin Lin^{2}, John McSorley^{3}, Caleb

Petrie^{4}, and Luc Teirlinck^{1}

1Department of Mathematics and Statistics, Auburn University, AL 36849

johnspd@auburn.edu 2University of California, Berkeley 3Department of Mathematics Southern Illinois University Carbondale, Illinois 62901-4408 4Biola University

Abstract A finite simple graph is uniformly (t, r)-regular if it has at least t vertices and the open neighbor set of each set of t of its vertices is of cardinality r. If t > 1, such a graph is trivially uniformly (t, r)-regular if either it is a matching (t = r) or r is the number of non-isolated vertices in the graph. We prove the result stated in the title.

1 Uniform (t, r)-regularity

All graphs will be finite and simple, in this paper, and notation will largely be as in [10]. If G and H are graphs, V (G) is the vertex set of G, G+H is the disjoint union of G and H, and for a positive integer m, mG = G+⋯+G (m summands). If u ∈ V (G), N_{G}(u) = {v ∈ V (G)|u and v are adjacent in G}, and if S ⊆ V (G), N_{G}(S) = ⋃_{u∈S} N_{G}(u), the open neighbor set of S in G. The order of G will be denoted by n(G)(= |V (G)|), or just n, if G is the only graph in the discussion.

G is uniformly (t, r)-regular if 1 ≤ t ≤ n and for each S ⊆ V (G) with |S| = t, |N_{G}(S)| = r. This property of graphs was introduced in [4] as “(t, r)-regularity”; the problem with that terminology is that it is also used for a seemingly similar but rather less exigent property, introduced in [3] and written on in [2], [5], and [7]. In [6] the word “strong” plays the role we assign to “uniform” here; we abandon that terminology because it misleadingly suggests an analogy with strong regularity of graphs. There is a powerful connection between the two when t = 2 (see [9]), but the analogy at the definitional level is distant.

Uniform (1, r)-regularity is just plain r-regularity. When t > 1 there are two easily found classes of uniformly (t, r)-regular graphs:

(i) G = mK_{2} for some m ≥ t/2, a matching. In this case, t = r.

(ii) r = n(G_{1}), where G_{1} is the subgraph of G induced by the non-isolated vertices of G, and t is “sufficiently large”. Indeed, as noted in [6], if r = n(G_{1}) > 0 and n(G) − δ(G_{1}) + 1 ≤ t ≤ n(G) then G is uniformly (t, r)-regular, but G is not uniformly (n(G) − δ(G_{1}), r)-regular. And if r = n(G_{1}) = 0 then G = nK_{1} and is uniformly (t, 0)-regular for all t = 1, …, n.

For t > 1, uniform (t, r)-regularity due to either condition (i) or (ii) will be called trivial, and the big question (raised in [6]) is: are there non-trivially uniformly (t, r)-regular graphs, and, if so, what are they?

This question has been satisfactorily answered for t = 2. Any “strongly regular graph with λ = μ > 0”, that is, a regular graph G, say with degree d > 0, not complete, for which there exists μ such that for any two distinct u, v ∈ V (G), |N_{G}(u) ∩ N_{G}(v)| = μ, is non-trivially uniformly (2, 2d − μ)- regular. There are infinitely many such graphs (see, e.g., [8]), and it has recently been shown [9] that there are no other non-trivially uniformly (2, r)- regular graphs besides these. Here we settle the question for t > 2. The proof of the following theorem is postponed until section 3.

Theorem 1 If t > 2 then for no r does there exist a non-trivially uniformly (t, r)-regular graph.

2 An excursion into designs

If n ≥ t > 0, an (n, t, λ)-design is a pair (V, B) where V is a set with n elements (“points”) and B = [B(i)|i ∈ I] is an indexed collection of subsets of V (“blocks”) such that for each T ⊆ V with |T | = t, |{i ∈ I|T ⊆ B(i)}| = λ. (That is, any t points of V lie together in exactly λ blocks.) We require B to be an indexed collection because we want to allow “repeated blocks”; that is, it may be that B(i) = B(j) even though i ≠ j. Also note that there is no requirement that the blocks be of the same size. Given such a design, let b = |I|, the number of blocks.

Fisher’s Inequality [1, Theorem 2.6, p.66] If (V, B) is an (n, 2, λ)-design with λ > 0 and V not appearing as a block, then b ≥ n.

Theorem 2 If t > 2, λ > 0, and (V, B) is an (n, t, λ)-design with V not appearing as a block, then b ≥ n with equality if and only if B can be reindexed to be [V \{v}|v ∈ V].

Proof. We go by induction on t, starting with t = 3. For each v ∈ V, let I(v) = {i ∈ I|v ∈ B(i)} and consider the derived design (V \{v}, B′(v)), where B′(v) = [B(i)\{v}|i ∈ I(v)]. Each derived design is an (n − 1, 2, λ)- design (because t = 3) and V \{v} does not appear in B′(v) because V does not appear in B. By Fisher’s inequality, b′(v) = |I(v)| ≥ n − 1. On the other hand, b′(v) ≤ b.

If b = n − 1, then b′(v) = n − 1 = b, for every v ∈ V, so I(v) = I for every v. But then v ∈ B(i) for every i ∈ I, and every v, so, not only does V appear in B, it is equal to B(i) for each i, wildly contrary to hypothesis. So b ≥ n, as asserted. Suppose that b = n. Then b′(v) = |I(v)| = n or n − 1 for each v ∈ V –i.e., v is in every block of B or in every block but one.

On the other hand, each block of B is missing some element of V. Think of a bipartite graph with bipartition V, I, with v ∈ V adjacent to i ∈ I if and only if v ∉ B(i). Then each v ∈ V has degree ≤ 1 in this graph, and each i ∈ I has degree ≥ 1, and |V | = n = b = |I|. Thus the bipartite graph is a matching, and B, possibly after renaming, is [V \{v}|v ∈ V].

Now suppose that t > 3. With I(v) and B′(v), v ∈ V, defined as above, each derived design (V \{v}, B′(v)) is an (n − 1, t − 1, λ)-design, with V \{v} not among the blocks in B′(v). By the induction hypothesis, b ≥ b′(v) = |B′(v)| ≥ n − 1 for each v ∈ V. From here the proof proceeds as in the case t = 3.

3 Proof of Theorem 1

Lemma 1 If t > 1 and G is non-trivially uniformly (t, r)-regular, then G has no isolated vertices.

Proof. Suppose that u is an isolated vertex of G. Let G_{1} be the subgraph of G induced by the non-isolated vertices of G. Since G is non-trivial, 0 < r < n(G_{1}), and, therefore, t < n(G_{1}). Let S be a (t−1)-subset of V (G_{1}), and T = S ∪ {u}; then |N_{G}(T)| = |N_{G}(S)| = r. Since r < n(G_{1}), there is some w ∈ V (G_{1})\N_{G}(S), and, by the definition of G_{1}, some v ∈ V (G_{1}) adjacent to w. But then |S ∪ {v}| = t while |N_{G}(S ∪ {r})| ≥ r + 1, contradicting the assumption that G is uniformly (t, r)-regular.

The main idea that starts the proof of Theorem 1 is due to Khodkar and Leach [8]. Suppose that G is non-trivially (t, r)-regular, t ≥ 3. For v ∈ V (G), let B(v) = V (G)\N_{G}(v), and B = [B(v)|v ∈ V (G)]. By the Lemma, no v ∈ V (G) is isolated, so B(v) ≠ V (G). Further, r < n (nontriviality of G) and (V (G), B) is an (n, t, n − r)-design, with b = |V (G)| = n. Since t ≥ 3, by Theorem 2, for each v ∈ V (G) there is a u ∈ V (G) such that B(v) = V (G)\{u}. Thus G is a matching, and is thus trivially uniformly (t, r)-regular, after all.

References

[1] T. Beth, D. Jungnickel, and H. Lenz, Design Theory, Second Edition, Cambridge University Press, 1999.

[2] R. Faudree and D. Knisley, The characterization of large (2, r)-regular graphs, Congressus Numerantium 121 (1996), 105-108.

[3] T. Haynes and D. Knisley, Generalized maximum degree and totally regular graphs, Utilitas Mathematica 54 (1998), 211-221.

[4] Teresa W. Haynes and Lisa R. Markus, Generalized maximum degree, Utilitas Mathematica 59 (2001), 155-165.

[5] R. E. Jamison and P. D. Johnson Jr., The structure of (t, r)-regular graphs of large order, Discrete Math. 272 (2003), 297-300.

[6] Robert Jamison, Peter Johnson, Lisa Markus, Evan Morgan, and Emine Yazici, Strong (t, r)-regularity, submitted.

[7] P. D. Johnson Jr. and E. J. Morgan, Sharpening the Faudree-Knisley theorem on (2, r)-regularity, Bulletin of the ICA 29 (2003), 21-26.

[8] A Khodkar and C. D. Leach, On (2, r)-regular graphs, to appear in the Bulletin of the ICA.

[9] Abdollah Khodkar, David Leach, and David Robinson, Every (2, r)- regular graph is strongly regular, submitted.

[10] Douglas B. West, Introduction to Graph Theory, Second Edition, Prentice Hall, 2001.