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:

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