Neighborhood Champions in Regular Graphs

J. P. McSorley and W. D. Wallis, Department of Mathematics, Southern Illinois University, Carbondale, IL 62901-4408. USA.

Abstract

For a vertex x in a graph G we define Ψ_{1}(x) to be the number of edges in the closed neighborhood of x. Vertex x^{∗} is a neighborhood champion if Ψ_{1}(x^{∗}) > Ψ_{1}(x) for all x ≠ x^{∗}. We also refer to such an x^{∗} as a unique champion. For d ≥ 4 let n_{0}(1, d) be the smallest number such that for every n ≥ n_{0}(1, d) there exists a n vertex d-regular graph with a unique champion. Our main result is that n_{0}(1, d) satisfies d+3 ≤ n_{0}(1, d) ≤ 3d+1. We also observe that there can be no unique champion vertex when d = 3.

1 Introduction

We assume the standard ideas of graph theory. All graphs considered in this paper will be connected. We sometimes specify the vertex-set V and edge-set E of a graph G by denoting the graph G(V, E). |V | and |E| are respectively the order and size of G. The distance d(v, u) between two vertices v and u in a graph is the number of edges in a shortest path from v to u. The closed k-neighborhood of a vertex v is defined as

N_{k}[v] = {u ∈ V : d(v, u) ≤ k}.

When k = 1 we simply use the term “neighborhood”.

The scale-k locality statistic Ψ_{k}(x) of vertex x in a connected graph G(V, E) was defined in [4] to be the size of the subgraph induced by the closed k-neighborhood of x. (This statistic is also called the number of edges seen by x.) The scale-k scan statistic M_{k}(G) of G was then defined to be the maximum over x ∈ V of the scale-k locality statistics:

M_{k}(G) = max_{x∈V} Ψ_{k}(x).

In a mild abuse of notation, we define Ψ_{0}(x) to be the degree of vertex x in G, and M_{0}(G) to be the maximum degree in G.

A champion for scale k is a vertex x^{∗} such that Ψ_{k}(x^{∗}) > Ψ_{k}(x) for all x ≠ x^{∗}. The reasons for studying champions are discussed in [4]; in that paper the authors discussed dramatic champions, for which Ψ_{k}(x^{∗}) >> Ψ_{k}(x) for all x ≠ x^{∗}. In [3] we construct some families of dramatic neighborhood champions, or champions for scale 1.

In this paper we focus on the pure graph theory of the situation, and consider the existence of neighborhood champions for scale 1 in connected regular graphs. We shall sometimes discuss graphs in which more than one vertex attains the maximum value M_{1}(G). We shall use the word “co-champion” to denote these vertices.

1.1 Groupies

A related, but different, concept to a champion in G is a groupie in G. No confusion should arise between the two: A vertex in G is a groupie if the average degree of its neighbors is greater than or equal to the average degree of G. The concept was introduced in [1] (see also [2]).

2 Cubic graphs: d = 3

Theorem 1. For d = 1, 2, and 3 there are no d-regular graphs with a unique neighborhood champion.

Proof Clearly regular graphs of degrees d = 1 or 2 have no champions.

Now suppose G is a cubic graph: If M_{1}(G) = 3 then every vertex attains M_{1}(G). If M_{1}(G) = 4, then any vertex x with Ψ_{1}(x) = 4 lies in exactly one triangle, and the other vertices of the triangle are co-champions; so G contains at least three co-champions. If M_{1}(G) = 5 and vertex x sees five edges, the configuration must be as shown in Figure 1, where y is a cochampion. And if M_{1}(G) = 6 (the maximum) we have G = K_{4}, and every vertex is a co-champion. Thus no cubic graph has a champion.

\begin{matrix}x \\ y \end{matrix}

Figure 1: A cubic configuration

However, one can construct cubic graphs with precisely two co-champions, or twin champions, for every even number n ≥ 10 of vertices. From above we must have M_{1}(G) = 5.

A short exhaustive search shows that this is impossible for fewer than 10 vertices (the graphs may be found on page 127 of [5]).

For every even n ≥ 10 we construct a cubic graph G on n vertices for which Ψ_{1}(x) = M_{1}(G) = 5 for precisely two vertices. Our technique is to implant the graph shown in Figure 2 as a subgraph of a host graph. The implant graph H has six vertices a, b, p, q, y, z and adjacencies ap, bq, yp, yq, zp, zq, yz.

a  p  y  q z  b

Figure 2: The graph H to be implanted

Construction Select any triangle-free cubic graph on n − 4 vertices and choose any edge ab in that graph. Delete this edge. Then identify vertices a, b with the vertices a, b of H. See Figure 3 for an example of this; the value of Ψ_{1}(x) is shown on each vertex and the champion is emphasized.

Ψ_{1}(y) = Ψ_{1}(z) = 5, Ψ_{1}(p) = Ψ_{1}(q) = 4 and Ψ_{1}(x) = 3 otherwise.

To show that the construction is always possible for n ≥ 10, we observe

Lemma 1. If n − 4 = 2s ≥ 6, there is a triangle-free cubic graph on n − 4 vertices.

Proof Take the integers modulo 2s as vertices. For each i, let vertex i be adjacent to vertices i − 1, i + 1, and i + s (modulo 2s).

(This graph is called a Möbius ladder [5, p263].)

So we have

Theorem 2. For every even n ≥ 10 there exists a cubic graph on n vertices with precisely two co-champions.

a  b  ^{33 3  3 33 4 55 4}

Figure 3: Example for 10 vertices

3 General Constructions: d ≥ 4

For even d ≥ 4 let n_{0}(c, d) be the smallest number such that for every n ≥ n_{0}(c, d) there exists a n vertex d-regular graph with precisely c neighborhood co-champions; for odd d we require existence for even n ≥ n_{0}(c, d) only.

In this section we discuss n_{0}(1, d).

The complete graph on n vertices is denoted K_{n}, while K_{m,n} denotes the complete bipartite graph with vertex-sets of sizes m and n. A one-factor is a graph consisting of disjoint edges; in particular, given two ordered sets of vertices Y = {y_{0}, y_{1}, …, y_{n−1}} and Z = {z_{0}, z_{1}, …, z_{n−1}}, we define the one-factor F_{j}^{n}(Y, Z) to consist of the edges

y_{0}z_{j}, y_{1}z_{1+j}, , …, y_{n−1}z_{n−1+j},

where subscripts are reduced modulo n. Then K_{n,n} can be represented as

F_{0}^{n}(Y, Z) ∪ F_{1}^{n}(Y, Z) ∪ … ∪ F_{n−1}^{n}(Y, Z).

Lemma 2. Suppose d ≥ 4. For every t ≥ 0 there exists a d-regular graph, with a neighborhood champion, on n = 3d + 2t + 1 vertices.

Proof Let H represent the complete graph on the d+1 vertices x_{0}, x_{1}, …, x_{d} with the d edges of the cycle x_{0}x_{1}x_{2} … x_{d−1} deleted. Take a copy of F_{0}^{n}(Y, Z)∪ F_{1}^{n}(Y, Z)∪…∪F_{d−1}^{n}(Y, Z), where n = d+t, and delete the edges y_{0}z_{0}, y_{1}z_{1}, …, y_{d−1}z_{d−1}. Adjoin this to H by adding edges x_{0}y_{0}, x_{0}z_{0}, x_{1}y_{1}, x_{1}z_{1}, …, x_{d−1}y_{d−1}, x_{d−1}z_{d−1}.

In this graph,

Ψ_{1}(x_{d}) = d(d − 1)/2,
Ψ_{1}(x_{i}) = (d^{2} − 5d + 14)/2, for 0 ≤ i ≤ d − 1,
Ψ_{1}(y_{j}) = Ψ_{1}(z_{j}) = d, for 0 ≤ j ≤ n − 1.

Then x_{d} is a champion provided d(d − 1)/2 > (d^{2} − 5d + 14)/2, that is d ≥ 4.

The above construction gives graphs whose order is of opposite parity to d. When d is odd, this provides all possible orders from some point on, because regular graphs of odd degree must have even order. However, for even degree, another construction is needed for even orders.

Suppose G is the graph of Lemma 2 in the case where d ≥ 4 is even. We modify G to form Ĝ as follows: Add a vertex x̂. Delete the d/2 edges x_{0}y_{0}, x_{2}y_{2}, x_{4}y_{4}, …, x_{d−2}y_{d−2}, and add the d edges x̂x_{0}, x̂y_{0}, x̂x_{2}, x̂y_{2}, x̂x_{4}, x̂y_{4}, …, x̂x_{d−2}, x̂y_{d−2}.

The Ψ_{1} values of all vertices of G are unchanged. We have Ψ_{1}(x̂) = d + \binom{d/2}{2} = (d^{2} + 6d)/8. Thus vertex x_{d} is still the champion, and we have

Lemma 3. Suppose d ≥ 4 is even. For every t ≥ 0 there exists a d-regular graph, with a neighborhood champion, on n = 3d + 2t + 2 vertices.

Theorem 3. Suppose d ≥ 4. Then

d + 3 ≤ n_{0}(1, d) ≤ 3d + 1.

Proof For any d ≥ 4 the only d-regular graph with d + 1 vertices is K_{d+1}, which clearly doesn’t have a unique champion. And for odd d ≥ 4 there is no d-regular graph with d + 2 vertices, so n_{0}(1, d) ≥ d + 3. And for even d ≥ 4 the only d-regular graph with d+2 vertices is K_{d+2} minus a one-factor, which again doesn’t have a unique champion; so n_{0}(1, d) ≥ d + 3 here also. Hence, for any d ≥ 4, we have n_{0}(1, d) ≥ d + 3. The upper bound n_{0}(1, d) ≤ 3d + 1 comes from Lemmas 2 and 3.

4 Small degrees: d = 4, 5

By inspection, there are no 4-regular (quartic) graphs on n = 7 or 8 vertices with a unique champion (see [5, p145]). From Theorem 3 and the examples for orders n = 9, 10, 11 and 12 shown in Figure 4 we see that n_{0}(1, 4) = 9, i.e., there is a 4-regular graph, with a neighborhood champion, on n vertices whenever n ≥ 9.

Similarly, at degree 5, inspection shows (see [5, p154]) there are no quintic graphs on n = 6 or 8 vertices with a unique champion. We present examples on 10, 12 and 14 vertices in Figure 5, showing that n_{0}(1, 5) = 10. Thus there is a 5-regular graph, with a neighborhood champion, on n vertices for every even n ≥ 10. So the cases of d = 4 or 5 are completely solved.

7  _{6}  _{8}  _{6}  _{7}_{7}_{6}^{6}^{7} 9 vertices  ^{^{7}^{5}  ^{6}  ^{6}  ^{6}_{5}  _{6}  _{6}  _{6}_{5} 10 vertices}
7^{6}  ^{6}  ^{6}  ^{6}^{5}  ^{4}  ^{4}  ^{5}_{5}  _{5} 11 vertices  ^{^{6}  ^{6}  ^{4}  ^{4}  ^{4}^{8}  ^{4}^{6}  ^{6}  ^{4}  _{4}  ^{4} 12 vertices}

Figure 4: Small quartic graphs, each with a champion

9  ^{11}  ^{9}^{9}  ^{8}  ^{9}_{10}  _{10}_{10}  _{10} 10 vertices

12_{9}  _{9}  _{10}  _{10}  _{7}_{9}  _{9}  _{9}  _{9}  _{9}  _{9} 12 vertices

12^{9}  ^{9}  ^{10}  ^{10}  ^{8}_{8}  _{8}  _{9}  _{9}  _{9}  _{9}_{10}  _{10} 14 vertices Figure 5: Small quintic graphs, each with a champion

5 Directions for future work

In our constructions above of a d-regular graph with a unique champion we allowed the function Ψ_{1} to take on as many values as the construction demanded. In some applications it is desirable to restrict the range of Ψ_{1} to just two values, namely Ψ_{1}(x^{∗}), the value of Ψ_{1} at the champion vertex x^{∗}, and Ψ_{1}(x) for all other vertices x ≠ x^{∗}. Some graphs with this property were constructed in [4], and the existence of further graphs is an area for future research.

Another problem is the existence of regular graphs with precisely two co-champions. We discussed the d = 3 case earlier; some further results have been obtained and will be the subject of a future paper.

References

[1] M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers. J. Combinatorial Theory 29A (1980), 354-360.

[2] E. Bertram, P. Erdös, P. Horák, J. S̆irán̆ and Zs. Tuza, Local and global average degree in graphs and multigraphs. J. Graph Theory 18 (1994), 647–661.

[3] J. P. McSorley, C. E. Priebe and W. D. Wallis, Neighborhood Champions. (In preparation)

[4] C. E. Priebe and W. D. Wallis, On the Anomalous Behaviour of a Class of Locality Statistics. Discrete Math. 308 no.10 (2008), 2034–2037.

[5] R. C. Read and R. J. Wilson, An Atlas of Graphs (Oxford U.P., 1999).