IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 50 (2012), 1182
ISSN 2232-2094
MOORE GRAPHS AND CYCLES ARE EXTREMAL GRAPHS FOR CONVEX CYCLES
Jernej Azarija Sandi Klavžar
Ljubljana, October 24, 2012
сч
i-Ч
О
сч сч
CD
гО
О
О
СО
и
а
CD U Оч
Moore graphs and cycles are extremal graphs for convex
cycles
Jernej Azarija Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia jernej.azarija@gmail.com
Sandi KlavZar
Faculty of Mathematics and Physics, University of Ljubljana Jadranska 19, 1000 Ljubljana, Slovenia and
Faculty of Natural Sciences and Mathematics, University of Maribor Koroska 160, 2000 Maribor, Slovenia sandi.klavzar@fmf.uni-lj.si
October 12, 2012
СЧ CO
Let p(G) denote the number of convex cycles of a simple graph G of order n, size m, and girth 3 < g < n. It is proved that p(G) < ^ (m — n + 1) and that equality holds if and only if G is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving
CO
a new characterization of Moore graphs.
CO
Keywords: convex subgraph; convex cycle; Moore graph; extremal graph
Abstract
AMS Subj. Class. (2010): 05C75, 05C12 1 Introduction
-4
Convexity is a central notion in the theory of discrete metric spaces [28]. In graph theory, convex subgraphs and in particular convex cycles are often employed to unveil additional structure of the studied graphs. Recall that a subgraph H of a graph G is convex if for any u,v G V (H ), every shortest u, v-path in G lies completely in H. In particular, if H is convex in G, then dH (u, v) = dG(u,v) holds for any u, v G V (H), where dG denotes the usual shortest path distance in G.
О
сч
сч
U
CD
О
О
сч 00
Convex subgraphs are indispensable in the study of (Cartesian) graph products. Extending a result of Vanden Cruyce [27] for hypercubes, Egawa [11] characterized Cartesian products of complete graphs by convex subgraphs. Similarly, Chepoi [8] characterized isometric subgraphs of Cartesian products of complete graphs via convexity of certain subgraphs. In [1] weak Cartesian products of trees are characterized among median graphs by the property that K2,3 minus an edge is not a convex subgraph. For additional aspects on the convexity of graph products see [13]. For instance, the book contains a short proof of the classical unique prime factorization theorem with respect to the Cartesian product, where convexity is the key tool for the short proof.
Convex subgraphs are even more important in understanding the structure of isometric subgraphs of hypercubes, graphs known as partial cubes. (Recall that median graphs form a distinguished subclass of partial cubes.) It all started with the seminal paper of Djokovic [10] in which partial cubes are characterized among bipartite graph with the convexity of subgraphs induced by vertices closer to one endpoint of an edge than to the other. Later, Bandelt and Chepoi [2] characterized acyclic cubical complexes among median graphs by forbidden convex subgraphs. These graphs were further characterized as the graphs for which —2 is a zero of the cube polynomial of an arbitrary 2-connected convex subgraph [5].
Among convex subgraphs, convex cycles are frequently studied. In [21] Polat proved that a netlike partial cube is prism-retractable if and only if it contains at most one convex cycle of length greater than 4 while in [22] he showed that any netlike partial cube that is without an isometric ray contains a convex cycle or a finite hypercube which is fixed by every automorphism. Parallel to the first mentioned Polat's result it was proved in [18] that a partial cube is almost-median
CSI
if and only if it contains no convex cycle of length greater than 4. Very recently the convex excess of a graph was introduced as the sum of contributions of all of its convex cycles and used to obtain an inequality involving the order, the size, the isometric dimension, and the convex excess of an arbitrary partial cube [17].
Here we consider convex cycles from an extremal point of view: what is the largest number of convex cycles that a given graph can have? We became interested in this question because of the recent paper [15] by Hellmuth, Leydold, and Stadler in which convex cycle bases are studied. Along the way they also proved that a graph G of order n and size m contains at most nm convex cycles. In this paper we strengthen this by proving the following result.
О
CSI
I
Theorem 1 Let G be a simple graph of order n, size m, and girth g > 3. Then G contains at most
n
g (m — n +1)
convex cycles. Moreover, equality holds if and only if G is an even cycle or a Moore
U
a
CD U 0ч
graph.
О
сч
Recall that a Moore graph is a graph with the maximum possible number of vertices that a given graph with prescribed maximum degree and diameter can have. Equivalently, a Moore graph can also be defined as a graph with diameter r and girth 2r + 1, cf. [12, p. 90]. Singleton [26] proved that Moore graphs are regular, see [12, Lemma 5.8.1] for an elegant proof. The only Moore graphs that exist are complete graphs, odd cycles, the Petersen graph, the Hoffman-Singleton graph, and possibly a Moore graph of diameter 2 and degree 57 [16, 3, 9]. The existence of a latter Moore graph is a big open problem. As a by-product of teh proof of Theorem 1, we also get:
СЧ CD
О
О
сч 00
о
Theorem 2 Let G be a simple graph of order n, size m, and girth g = 2r +1. Then G is a Moore graph if and only if the number of (2r+1)-cycles in G is 2+1 (m-n+1).
For detailed information on Moore graphs and related classes of graphs see the survey [20]. The recent paper [19] contains further insights into a missing Moore graph. In particular it is proved that the order of the automorphism group of such a graph is at most 375 thus significantly extending the fact that it is not vertex-transitive as proved Graham Higman in a series of lectures, cf. [6, Theorem 3.13]. On the other hand Siagiova and Siran [25] proved that for an infinite set of degrees r there exist vertex-transitive graphs of degree r, diameter 2, and order close to the Moore bound.
The next section contains the proof of Theorems 1 and 2, a concluding remark is given in the final section.
00
2 Proof of Theorem 1
СЧ
This section is organized as follows. We first characterize convex cycles in a way suitable to us. In the following subsection the number of odd convex cycles of a given graph is bounded and proved that precisely the Moore graphs are extremal graphs. In Subsection 2.2 we then prove a corresponding upper bound for even convex cycles while in the last subsection a combined inequality is derived.
In what follows G will denote a simple graph on n vertices, with m edges, and of girth g > 3. The following characterization of convex cycles is a modification of a related result proved in [15]. More precisely, the first part (for odd cycles) is the same, while the second part is modified to serve our purposes.
Lemma 3 Let C be a cycle of G. If | C| = 2k + 1, k > 1, then C is convex if and only if for every edge e = xy of C there exists a vertex v G C such that
U
(i)	dG(x,v) = dG(y,v) = k, and
CO
(ii)	the x,v-path (resp. y,v-path) on C of length k is a unique shortest x,v-path
(resp. y,v-path) in G.
• и
о О
CSI
If |C| =2k, k > 2, then C is convex if and only if for every vertex u G C there exists a vertex v G C such that
"ŠT
(iii)	dG(u, v) = k,
(iv)	there are precisely two u,v-paths in G of length k.
Proof. As mentioned above, we only need to prove the even case. Hence let |C| = 2k, k > 2. It is clear that the two conditions are necessary. Suppose now that for every vertex u G C there exists a vertex v G C such that (iii) and (iv) hold. By way of contradiction assume that there are vertices x, y G C such that there is shortest x, y-path P that is not completely contained in C. Let x' be the vertex on C with dG(x,x') = k. By (iv) there are precisely two x,x'-paths in G of length k and they are both contained in C. Then y belongs to one of these paths, denote it with Q. If P is shorter than the length of the x,y-subpath of Q, then dG(x,x') < k, a contradiction. And if P is of the same length as the x,y-subpath of Q, then we would have at least three x, x'-paths of length k, which contradicts (iv) for x and x'.	□
For later use we note here that if follows from the first part of Lemma 3 that in a graph of girth g = 2r + 1 all of its g-cycles are convex.
We will call a pair (e, v) G E(G) x V(G) that satisfies conditions (i) and (ii) of Lemma 3 an odd antipodal pair. Likewise if (u, v) G V (G) x V (G) satisfies conditions (iii) and (iv) then we will say that (u, v) is an even antipodal pair. In cases where the context is clear we will simply say that a pair (a, b) is antipodal if it is an even or odd antipodal pair.
Observe that Lemma 3 readily implies that the number of odd convex cycles is O(nm) while the number of even convex cycles is O(n2). In what follows we give sharper estimates for these two quantities by bounding the number of antipodal pairs.
CO CO
2.1 Odd convex cycles
Lemma 4 For any vertex v G V (G) there are at most m — n + 1 edges e such that (e, v) is an odd antipodal pair.
Proof. Let T be a BFS tree of G with root v. Then the assertion readily follows from the fact that if e G E (T), then one endpoint of e is closer to v than the other. Consequently, (e, v) is not antipodal.	□
'H
S_!
From Lemma 4 we get an estimate on the number of odd convex cycles in G, which we denote by po(G).
U
a
CD U Оч
Lemma 5 po(G) < n(m — n + 1).
Proof. Suppose that G contains k odd convex cycles. Every convex cycle C determines precisely |C| > g antipodal pairs. We select one and assign it to C. Doing it for every convex cycle, there are at least k(g — 1) antipodal pairs that are not assigned to convex cycles. In addition, by Lemma 4, a vertex of G does not form an antipodal pair with at least n — 1 edges. Therefore we have at least n(n — 1) non-antipodal pairs. If follows that
о
k < nm — k(g — 1) — n(n — 1)
and thus
n
k < — (m — n + 1) g
as claimed.	□
СЧ
и
CD
If G is a cycle, then m = n = g, thus the bound of Lemma 5 is sharp for all odd cycles. The same holds for complete graphs Kn, n > 3. Indeed, for Kn we have g = 3, m = (n), and any triple of vertices induces a triangle, hence the assertion follows because П ( (П) — n + 1) = (П). We next show that equality in Lemma 5 holds precisely for the Moore graphs.
Lemma 6 po(G) = n(m — n + 1) if and only if G is a Moore graph.
Proof. Suppose first that G is a graph that satisfies the equality. Then it follows from Lemma 5 and its proof that the girth g of G is odd and that all convex cycles 00 of G are of length g = 2r + 1. Recall from Lemma 4 that a vertex v G V (G) CSI lies in at most m — n + 1 antipodal pairs. Since the equality is satisfied for G, it follows that every edge which is not on a BFS tree with a root v constitutes an antipodal pair with v. In other words every such edge joins two vertices x,y such that dG(v,x) = dG(v,y) = r. Consider now a BFS tree T rooted at v and let v' be a leaf of T. Observe that v' has degree at least two in G because p(G) = p(G — u) holds for any pendant vertex u. Hence there is an edge e not in T that is adjacent to v' in G. From the above remark it follows that (e, v) is an antipodal pair and therefore dG(v,v') = r. This in turn implies that G has diameter r. Since the girth of G is 2r + 1 we conclude that G is a Moore graph.
To prove the converse we need to show that every Moore graph satisfies the equality. As already observed, this is the case with odd cycles and complete graphs of order n > 3. The Petersen graph has girth 5, hence all of its twelve 5-cycles are convex. Since 10(15 — 10 + 1) = 12, the bound for the Petersen graph is established.
It thus remains to show that the Hoffman-Singleton graph H and a possible Moore graph X of diameter 2 and degree 57 also have the claimed property. To show this we use an implication of a result of Harary [14] which can be formulated as follows, cf. [4, p. 45]. Let pG(x) be the characteristic polynomial of a graph G of
Ö
О
сч
CSI
order n and odd girth g. Then the number of g-cycles of G equals —c/2, where c is the coefficient at xn-a in pG(x).
The Hoffman-Singleton graph H has 50 vertices, 175 edges, and p4(x) = (x — 7)(x — 2)28(x + 3)21, cf. [23]. Since it has girth 5 and
(ЩШРИ(x)) (0) --45! = —2520 '
О
О
со
со
и
а
CD U
it follows that the number of 5-cycles of H is 1260. Hence the bound of Lemma 6 is sharp for H.
For the possible Moore graph X it is known that px(x) = (x — 57)(x + 8)1520(x — 7)1729, cf. [19, Proposition 1]. Since the coefficient of x3245 in the polynomial px(x) is —116188800 it follows that X has 58094400 5-cycles. Given the fact that X has degree 57 and order 3250, it is now straightforward to verify that X also satisfies the equality.	□
О
Theorem 2 now follows immediately from Lemma 6. 2.2 Even convex cycles
We next derive an upper bound for the number of even convex cycles, denoted with pe(G). The bound is similar to the above bound for po(G).
It follows from the second part of Lemma 3 that if (v,v') is an even antipodal pair then dG(v,v') > 2. Combining this with the fact that every even convex cycle C yields |C|/2 antipodal pairs, gives the bound
Pe (G) < n(n — 1) — 2m .
g
While this bound is of the right order, it is not very sharp for sparse graphs. The next result establishes a better bound for graphs with a small cyclomatic number, that is, with a small m — n + 1.
Lemma 7 pe(G) < n(m — n + 1). Moreover, equality holds if and only if G is an even cycle.
Proof. We claim that every vertex v G V (G) lies in at most m — n + 1 even antipodal pairs. Let (v, v') be an antipodal pair of vertices from an even convex cycle C. Let T be a BFS tree rooted at v. Lemma 3 implies that all the edges of C are on T with the exception of one edge e that is incident with v' on C. So for every vertex CD v' that is antipodal with v there is at least one edge e not on T that is adjacent to v'. This proves the claim. In total we therefore have at most n(m — n + 1) even
antipodal pairs. In addition, every even convex cycle of length 2k yields k antipodal pairs. Since we only need to count unordered pairs, we deduce that
Pe(G) < n(m - n + 1). 9
CD
For the equality part of the lemma, let C be an even convex cycle of G. If G = C then equality clearly holds. Otherwise, let u be a vertex of G that is not on C and is adjacent to a vertex v G C. Let v' be the antipodal vertex of v on C. Then observe that (u, v') is not an antipodal pair. Moreover, at least one edge that is incident with v' on C is not on a BFS tree rooted at u. We deduce that u is contained in less
О
О
than m — n +1 even antipodal pairs which implies that G has less than n (m — n +1) even convex cycles.	□
2.3 A combined inequality
О
We finally combine the derived bounds for po(G) and pe(G) into a single inequality for the number p(G) of all convex cycles of G. The key insight is that graphs with the maximum number of convex cycles are homogeneous in the sense that they either contain only even or only odd convex cycles. The following lemma establishes this fact.
CD CO
U
a
CD U Оч
Lemma 8 p(G) < n (m — n + 1). Moreover, if G contains an even convex cycle then the bound is attained if and only if G = Cn.
Proof. Suppose that C is an even convex cycle of G. Let v G C and consider a BFS tree T rooted at v. Let v' be the antipodal vertex of v with respect to C. Let e and f be the edges of C incident with v'. Then at least one of these two edges is not on T and hence does not form an antipodal pair with v. This means that for every CO even convex cycle there is at least one less possible odd convex cycle which in turn implies that
n
p(G) < - (m — n + 1).
Suppose now that G contains an even convex cycle C and that G = Cn. Let u G C be a vertex of G that is adjacent to a vertex v G C. Let v' be the antipodal vertex of v on C and consider a shortest u, v'-path Puv/. We distinguish two cases and wish to show that the given configuration forbids the attainment of the bound.
Case 1. Puv, n C = 0.
In this case (u, v') is not an antipodal pair of an even convex cycle. Moreover at least one edge incident with v' on C is not in a BFS tree rooted at u and also does not form an antipodal pair with u. The latter fact implies that p(G) < n (m — n +1).
сч
Jh
CD
О
О
S
СО
со
со
CD
'Н
CD СО
и
а
CD U
Case 2. Puv, П C = 0.
In this case the degree of v' is at least 3 and, because C is convex, |PuV1 = dG(v, v'). It follows that a BFS tree T rooted at u does not contain the edges e and f that are on C incident with v. Moreover, none of these two edges forms an antipodal pair with u. Since (u, v') is an antipodal pair of at most one even convex cycle, u is contained in strictly less than m — n + 1 antipodal pairs. Therefore the inequality for p(G) is again not attained.	□
Theorem 1 now follows by combining Lemma 8 with the results of Subsections 2.1 and 2.2.
3 Concluding remark
i—i
In this paper we have characterized the graphs in which the upper bound for the number of convex cycles n (m — n + 1) is attained. It turned out that there are not many such graphs. In might hence be interesting to study graphs that are close to this bound. A reasonable class of graphs in this respect could be generalized Moore graphs [7, 24] as it appears that they contain many (even) convex cycles.
"ŠT
Acknowledgments
СЧ
This work has been financed by ARRS Slovenia under the grant P1-0297 and within the EUROCORES Programme EUROGIGA/GReGAS of the European Science Foundation. The second author is also with the Institute of Mathematics, Physics
and Mechanics, Ljubljana.
References
[1]	H.-J. Bandelt, G. Burosch, J.-M. Laborde, Cartesian products of trees and paths, J. Graph Theory 22 (1996) 347-356.
[2]	H.-J. Bandelt, V. Chepoi, Graphs of acyclic cubical complexes, European J. Combin. 17 (1996) 113-120.
[3]	E. Bannai, T. Ito, On finite Moore graphs, J. Fac. Sci. Univ. Tokyo Sect. IA Math. 20 (1973) 191-208.
[4]	N. L. Biggs, Algebraic Graph Theory. Second Edition, Cambridge University Press, Cambridge, 1993.
[5]	B. Bresar, S. KlavZar, R. Skrekovski, Roots of cube polynomials of median
graphs, J. Graph Theory 52 (2006) 37-50.
[6] P. Cameron, Permutation Groups, Cambridge University Press, Cambridge, 1999.
СЧ	[7] V. G. Cerf, D. D. Cowan, R. C. Mullin, R. Stanton, Computer networks and
generalized Moore graphs, in: Proceedings of the Third Manitoba Conference on Numerical Mathematics (Winnipeg, 1973) (1974) 379-398.
[8]	V. Chepoi, d-Convexity and isometric subgraphs of Hamming graphs, Cybernetics 1 (1988) 6-9.
[9]	R. M. Damerell, On Moore graphs, Proc. Cambridge Philos. Soc. 74 (1973) 227-236.
[10] D. Djokovic, Distance preserving subgraphs of hypercubes, J. Combin. Theory Ser. B 14 (1973) 263-267.
О Ö
CO CO
[11] Y. Egawa, Characterization of the Cartesian product of complete graphs by convex subgraphs, Discrete Math. 58 (1986) 307-309.
[12]	C. Godsil, G. Royle, Algebraic Graph Theory, Springer, New York, 2001.
[13]	R. Hammack, W. Imrich, S. KlavZar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011.
СЧ
[14]	F. Harary, The determinant of the adjacency matrix of a graph, SIAM Review 4 (1962) 202-210.
CO
[15]	M. Hellmuth, J. Leydold, P. F. Stadler, Convex cycle bases and Cartesian
CSI
products, manuscript, 2011.
[16]	A. J. Hoffman, R. R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. Res. Develop. 4 (1960) 497-504.
[17]	S. KlavZar, S. Shpectorov, Convex excess in partial cubes, J. Graph Theory 69 (2012) 356-369.
[18]	S. KlavZar, S. Shpectorov, Characterizing almost-median graphs II, Discrete Math. 312 (2012) 462-464.
[19]	M. Macaj, J. Siran, Search for properties of the missing Moore graph, Linear Algebra Appl. 432 (2010) 2381-2398.
CD
[20]	M. Miller, J. Siras, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin., Dynamic Survey DS14 (2005) 61 pp.
m
[21]	N. Polat, Netlike partial cubes. II. Retracts and netlike subgraphs, Discrete Math. 309 (2009) 1986-1998.
• и
[22]	N. Polat, Netlike partial cubes. IV. Fixed finite subgraph theorems, European J. Combin. 30 (2009) 1194-1204.
"ŠT
[23]	P. Rowlinson, I. Sciriha, Some properties of the Hoffman-Singleton graph, Appl. Anal. Discrete Math. 1 (2007) 438-445.
CD
[24]	M. Sampels, Vertex-symmetric generalized Moore graphs, Discrete Appl. Math. 138 (2004) 195-202.
О
О
[25] J. Siagiova, J. Siran, Approaching the Moore bound for diameter two by Cayley graphs, J. Combin. Theory Ser. B 102 (2012) 470-473.
[26]	R. Singleton, There is no irregular Moore graph, Amer. Math. Monthly 75 (1968) 42-43.
[27]	P. Vanden Cruyce, A characterization of the n-cube by convex subgraphs, Discrete Math. 41 (1982) 109-110.
О
[28]	M. L. J. van de Vel, Theory of Convex Structures, North-Holland Publishing Co., Amsterdam, 1993.
CO CD
'H
CD CO
CD CU