 Author
 Kris Coolsaet (UGent) , PD, Jr Johnson, KJ Roblee and TD Smotzer
 Organization
 Abstract
 We consider the class ER(n, d, lambda) of edgeregular graphs for some n > d > lambda, i.e., graphs regular of degree d on n vertices, with each pair of adjacent vertices having lambda common neighbors. It has previously been shown that for such graphs with lambda > 0 we have n >= 3(d  lambda) and much has been done to characterize such graphs when equality holds. Here we show that n >= 3(d  lambda) + 1 if lambda > 0 and d is odd and contribute to the characterization of the graphs in ER(n, d, lambda), lambda > 0, n = 3(d  lambda) + 1 by proving some lemmas about the structure of such graphs, and by classifying such graphs that satisfy a strong additional requirement, that the number t = t(u, v) of edges in the subgraph induced by the lambda common neighbors of any two adjacent vertices u and v is positive, and independent of u and v. The result is that there are exactly 4 such graphs: K4 and 3 strongly regular graphs.
Downloads

(...).pdf
 full text
 
 UGent only
 
 
 135.86 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU3099968
 Chicago
 Coolsaet, Kris, PD Johnson Jr, KJ Roblee, and TD Smotzer. 2012. “Some Extremal Problems for Edgeregular Graphs.” Ars Combinatoria 105: 411–418.
 APA
 Coolsaet, K., Johnson, P., Jr, Roblee, K., & Smotzer, T. (2012). Some extremal problems for edgeregular graphs. ARS COMBINATORIA, 105, 411–418.
 Vancouver
 1.Coolsaet K, Johnson P Jr, Roblee K, Smotzer T. Some extremal problems for edgeregular graphs. ARS COMBINATORIA. 2012;105:411–8.
 MLA
 Coolsaet, Kris, PD Johnson Jr, KJ Roblee, et al. “Some Extremal Problems for Edgeregular Graphs.” ARS COMBINATORIA 105 (2012): 411–418. Print.
@article{3099968, abstract = {We consider the class ER(n, d, lambda) of edgeregular graphs for some n {\textrangle} d {\textrangle} lambda, i.e., graphs regular of degree d on n vertices, with each pair of adjacent vertices having lambda common neighbors. It has previously been shown that for such graphs with lambda {\textrangle} 0 we have n {\textrangle}= 3(d  lambda) and much has been done to characterize such graphs when equality holds. Here we show that n {\textrangle}= 3(d  lambda) + 1 if lambda {\textrangle} 0 and d is odd and contribute to the characterization of the graphs in ER(n, d, lambda), lambda {\textrangle} 0, n = 3(d  lambda) + 1 by proving some lemmas about the structure of such graphs, and by classifying such graphs that satisfy a strong additional requirement, that the number t = t(u, v) of edges in the subgraph induced by the lambda common neighbors of any two adjacent vertices u and v is positive, and independent of u and v. The result is that there are exactly 4 such graphs: K4 and 3 strongly regular graphs.}, author = {Coolsaet, Kris and Johnson, PD, Jr and Roblee, KJ and Smotzer, TD}, issn = {03817032}, journal = {ARS COMBINATORIA}, language = {eng}, pages = {411418}, title = {Some extremal problems for edgeregular graphs}, volume = {105}, year = {2012}, }