Regular clique assemblies, configurations, and friendship in Edge-Regular graphs

Kelly B. Guest, James M. Hammer, Peter D. Johnson, Kenneth J. Roblee

Abstract


An edge-regular graph is a regular graph in which, for some $\lambda$, any two adjacent vertices have exactly $\lambda$ common neighbors. This paper is about the existence and structure of edge-regular graphs with $\lambda =1$ and about edge-regular graphs with $\lambda >1$ which have local neighborhood structure analogous to that of the edge-regular graphs with $\lambda =1$.

Full Text:

Remote PDF

References


A. E. Brouwer, Strongly Regular Graphs, Chapter VI.5 in The CRC Handbook of Combinatorial Designs, C. J. Colbourn, J. H. Dinitz, editors, CRC Press, New York, 1996, 667-685.

Peter J. Cameron, Strongly Regular Graphs, Chapter 12 in Selected Topics in Graph Theory, Lowell W. Beineke and Robin J. Wilson, editors, Academic Press, 1978, 337-360.

K. Coolsaet, P. D. Johnson Jr., K. J. Roblee, and T. D. Smotzer, Some extremal problems for edge-regular graphs, Ars Combinatoria, 105(2012), 411-418.

Harald Gropp, Configurations, Chapter VI.7 in The CRC Handbook of Combinatorial Designs, 2nd edition, C. J. Colbourn, J. H. Dinitz, editors, CRC Press, New York, 2006, 352-354.

Peter Johnson, Wendy Myrvold and Kenneth Roblee, More extremal problems for edge-regular graphs, Utilitas Mathematica, 73(2007), 159-168.

P. D. Johnson Jr. and K. J. Roblee, More extremal graphs for a maximum-joint-neighborhood, average-triangles-per-edge inequality, Congressus Numerantium, 140(1999), 87-95.

P. D. Johnson Jr. and K. J. Roblee, Non-existence of a nearly extremal family of edge-regular graphs, Congressus Numerantium, 203(2010), 161-166.

P. D. Johnson and K. J. Roblee, On an extremal subfamily of an extremal family of nearly strongly regular graphs, Australasian Journal of Combinatorics, 25(2002), 279-284.

J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd edition, Cambridge University Press, 2001.

Stephen C. Locke and Feng Lou, Finding independent sets in $K_4$-free 4-regular connected graphs, Journal of Combinatorial Theory, Series B, 71(1997), 85-110.

Michael W. Raney, On geometric trilateral-free $(n_3)$ configurations, Ars Mathematica Contemporanea, 6(2013), 253-259.

K. J. Roblee and T. D. Smotzer, Some extremal families of edge-regular graphs,25(2004), 927-933.

Edward Spence, Strongly Regular Graphs on at most 64 vertices, http://www.maths.gla.ac.uk/~es/




DOI: http://dx.doi.org/10.5556/j.tkjm.48.2017.2237

Sponsored by Tamkang University | ISSN 0049-2930 (Print), ISSN 2073-9826 (Online) | Powered by MathJax