Advanced search
1 file | 135.86 KB

Some extremal problems for edge-regular graphs

(2012) ARS COMBINATORIA. 105. p.411-418
Author
Organization
Abstract
We consider the class ER(n, d, lambda) of edge-regular 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: K-4 and 3 strongly regular graphs.

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 135.86 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Coolsaet, Kris, PD Johnson Jr, KJ Roblee, and TD Smotzer. 2012. “Some Extremal Problems for Edge-regular Graphs.” Ars Combinatoria 105: 411–418.
APA
Coolsaet, K., Johnson, P., Jr, Roblee, K., & Smotzer, T. (2012). Some extremal problems for edge-regular graphs. ARS COMBINATORIA, 105, 411–418.
Vancouver
1.
Coolsaet K, Johnson P Jr, Roblee K, Smotzer T. Some extremal problems for edge-regular graphs. ARS COMBINATORIA. 2012;105:411–8.
MLA
Coolsaet, Kris, PD Johnson Jr, KJ Roblee, et al. “Some Extremal Problems for Edge-regular Graphs.” ARS COMBINATORIA 105 (2012): 411–418. Print.
@article{3099968,
  abstract     = {We consider the class ER(n, d, lambda) of edge-regular 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: K-4 and 3 strongly regular graphs.},
  author       = {Coolsaet, Kris and Johnson, PD, Jr and Roblee, KJ and Smotzer, TD},
  issn         = {0381-7032},
  journal      = {ARS COMBINATORIA},
  language     = {eng},
  pages        = {411--418},
  title        = {Some extremal problems for edge-regular graphs},
  volume       = {105},
  year         = {2012},
}

Web of Science
Times cited: