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

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

doi:10.5556/j.tkjm.48.2017.2237

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

DOI: https://doi.org/10.5556/j.tkjm.48.2017.2237

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$.

Author Biographies

Kelly B. Guest

Department of Mathematics, Tuskegee University, Tuskegee, AL 36088, USA

James M. Hammer

Mathematics Department, Cedar Crest College, Allentown, PA 18104, USA.

Peter D. Johnson

Department ofMathematics and Statistics, Auburn University, Auburn, AL 36849-5310, USA

Kenneth J. Roblee

Department ofMathematics and Physics, Troy University, Troy, AL 36082, USA

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/