본문 바로가기
KERD
논문KCI 등재

The Gallai and Anti-Gallai Graphs of Strongly Regular Graphs

Jeepamol J. Palathingal|Aparna Lakshmanan S.|Greg Markowsky
경북대학교 자연과학대학 수학과|2024.03|Kyungpook Mathematical Journal|제64권 제1호|pp. 171-184|DOI https://doi.org/10.5666/KMJ.2024.64.1.171

2

조회

0

다운로드

0

인용

0

참고문헌

키워드

Gallai graphAnti-Gallai graphStrongly regular graphEdge-regular graphAdjacency spectrum
주제분류수학

초록

In this paper, we show that if G is strongly regular then the Gallai graph Γ(G) and the anti-Gallai graph ∆(G) of G are edge-regular. We also identify conditions under which the Gallai and anti-Gallai graphs are themselves strongly regular, as well as conditions under which they are 2-connected. We include also a number of concrete examples and a discussion of spectral properties of the Gallai and anti-Gallai graphs.

Abstract

In this paper, we show that if G is strongly regular then the Gallai graph Γ(G) and the anti-Gallai graph ∆(G) of G are edge-regular. We also identify conditions under which the Gallai and anti-Gallai graphs are themselves strongly regular, as well as conditions under which they are 2-connected. We include also a number of concrete examples and a discussion of spectral properties of the Gallai and anti-Gallai graphs.

참고문헌 (28)

  1. P. Anand, "On the hardness of recognizing triangular line graphs", Discrete Math., 312(17), pp.2627~2638 (2012)
  2. P. Anand, "Triangular line graph and word sense disambiguation", Discrete Appl. Math., 159(11), pp.1160~1165 (2011)
  3. S. Aparna Lakshmanan, "Characterization of some special classes of the Gallai and the anti-Gallai graphs", Discourse, 1, pp.85~89 (2013)
  4. S. Aparna Lakshmanan, "Gallai and anti-Gallai graphs of a graph", Math. Bohem., 132(1), pp.43~54 (2007)
  5. R. Balakrishnan, "A textbook of graph theory", pp.239~ (2000), Springer-Verlag
  6. R. B. Bapat, "Graphs and matrices", pp.205~ (2014), Springer
  7. L. W. Beineke, "Topics in algebraic graph theory" (2004), Cambridge University Press
  8. A. E. Brouwer, "The distance-regular graphs of valency four", J. Algebraic Combin., 10(1), pp.5~24 (1999)
  9. A. E. Brouwer, "The connectivity of strongly regular graphs", Euro-pean J. Combin., 6(3), pp.215~216 (1985)
  10. A. E. Brouwer, "Strongly regular graphs", pp.479~ (2022), Cambridge University Press
  11. P. J. Cameron, "Topics in Algebraic Graph Theory" (2004), Cambridge Univ. Press
  12. D. M. Cvetkovic, "Graphs and their spectra", Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., (354-356), pp.1~50 (1971)
  13. D. M. Cvetkovic, "Spectra of graphs", pp.447~ (1995), Johann Ambrosius Barth Verlag
  14. D. M. Cvetkovic, "An introduction to the theory of graph spectra", pp.376~ (2010), Cambridge University Press
  15. T. Gallai, "Transitiv orientierbare graphen", Acta Math. Acad. Sci. Hungar., 18, pp.25~66 (1967)
  16. P. Garg, "Eulerian and Hamiltonian properties of Gallai and anti-Gallai total graphs", J. Indones. Math. Soc., 21(2), pp.105~116 (2015)
  17. C. Godsil, "Algebraic graph theory", pp.659~ (2001), Springer-Verlag
  18. I. Gutman, "On the nullity of line graphs of trees", Discrete Math., 232, pp.35~45 (2001)
  19. F. Joos, "Forests and trees among Gallai graphs", Discrete Math., 338(2), pp.190~195 (2015)
  20. K. Kavitha, "Dominator coloring of some classes of graphs", Int. J. Math. Arch., 3(11), pp.3954~3957 (2012)
  21. V. B. Le, "Mortality of iterated Gallai graphs", Period. Math. Hungar., 27(2), pp.105~124 (1993)
  22. V. B. Le, "Gallai graphs and anti-Gallai Graphs", Discrete Math., 159, pp.179~189 (1996)
  23. J. J. Palathingal, "Gallai and anti-Gallai graph operators", Electron. Notes Discrete Math, 63, pp.447~453 (2017)
  24. J. J. Palathingal, "Spectrum of Gallai graph of some graphs", Indian J. Pure Appl. Math, 51(4), pp.1829~1841 (2020)
  25. A. Poovathingal, "Some characterizations of Gallai graphs", AIP Conference Proceedings, 2236(1), pp.060003~ (2020)
  26. A. Poovathingal, "A survey of the studies on Gallai and anti-Gallai graphs", Commun. Comb. Optim., 6(1), pp.93~112 (2021)
  27. E. Prisner, "Graph dynamics", pp.245~ (1995), Longman
  28. E. Sampathkumar, "The semi-total graphs of a graph II", J. Karnatak Univ. Sci., 18, pp.281~284 (1973)

관련 논문AI추천

A Relationship between the Second Largest Eigenvalue and Local Valency of an Edge-regular Graph박종육경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2021 · 제61권 제3호Distance-Regular Graphs with Valency k, Diameter D≥3 and at Most Dk+1 Vertices박종육경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2024 · 제64권 제3호On the Seidel Laplacian and Seidel Signless Laplacian Polynomials of GraphsB. Parvathalu, Daneshwari Patil, Harishchandra S. Ramane, K. Ashoka경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2021 · 제61권 제1호Quasi m-Cayley strongly regular graphsAleksander Malnic, Dragan Marusic, Klavdija Kutnar, Luis Martinez대한수학회 · 대한수학회지2013 · 제50권 제6호Integral Laplacian graphs with a unique repeated Laplacian eigenvalue, IIAbdul Hameed, Mikhail Tyaglov대한수학회 · 대한수학회보2025 · 제62권 제2호STRONGLY REGULAR GRAPHS OVER WEAK METRIC SCHEMES AND CHEEGER CONSTANTS OF HAMMING GRAPHS김길춘장전수학회 · Proceedings of the Jangjeon Mathematical Society(장전수학회 논문집)2017 · 제20권 제2호

이 간행물의 다른 논문 (11건)

A Characterization of Nonnil-Projective ModulesNajib Mahdou, 김환구, El Houssaine Oubouhoupp. 1-14Generalized Inverses and Solutions to Equations in Rings with InvolutionYue Sui, Junchao Weipp. 15-30Reverse Inequalities through k-weighted Fractional Operators with Two ParametersBouharket Benaissa, Noureddine Azzouzpp. 31-46A Study on Two Subclasses of Analytic and Univalent Functions with Negative Coefficients Involving the Poisson Distribution SeriesAbeer Omard Ahmad Badghaish, Fayzah Awad Alshehri, Abdul Moneim Yousof Lashinpp. 47-55Polylogarithms and Subordination of Some Cubic PolynomialsSukhjit Singh, Manju Yadav, Sushma Guptapp. 57-68
원문 보기