PBIB-Designs and 2-Steiner Distance Eigenvalues of Split Graphs

Authors

DOI:

https://doi.org/10.26713/cma.v15i3.2804

Keywords:

PBIB-design, Split graph, Steiner distance matrix, Spectrum

Abstract

In this paper, we have considered split graph Kn∘K1 with exactly four distinct adjacency eigenvalues. Since these graphs are not regular, it is laborious to construct block designs out of them. In this paper, we have shown the existence (hence construction) and non-existence of block designs arising out of split graphs Kn∘K1. In the second half of this paper, we have partially tried an NP-hard problem of finding 2-Steiner distance matrix of the split graph Kn∘K1. Furthermore, we have given interlacing for adjacency, distance and 2-Steiner distance spectra of split graph Kn∘K1. Time complexity and algorithm for finding rank of a matrix is given.

Downloads

References

W. Angaline and A. S. A. Mary, Minimum neighbourhood domination of split graph of graphs, Baghdad Science Journal 20(1) (2023), 273 – 276, DOI: 10.21123/bsj.2023.8404.

A. Azimi and S. Sivasubramanian, The 2-Steiner distance matrix of a tree, Linear Algebra and its Applications 655 (2022), 65 – 86, DOI: 10.1016/j.laa.2022.09.007.

A. Azimi, R. B. Bapat and S. Goel, Steiner distance matrix of caterpillar graphs, Special Matrices 10(1) (2022), 267 – 284, DOI: 10.1515/spma-2022-0162.

S. Banerjee, Distance energy change of complete split graph due to edge deletion, Discrete Mathematics, Algorithms and Applications 16(03) (2024), 2350033, DOI: 10.1142/S1793830923500337.

P. Bhunia, S. Bag and K. Paul, Bounds for eigenvalues of the adjacency matrix of a graph, Journal of Interdisciplinary Mathematics 22(4) (2019), 415 – 431, DOI: 10.1080/09720502.2019.1630938.

R. C. Bose and K. R. Nair, Partially balanced incomplete block designs, Sankhy¯a: The Indian Journal of Statistics 4(3) (1939), 337 – 372, URL: https://www.jstor.org/stable/40383923.

A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, New York, xiii + 250 pages (2012), DOI: 10.1007/978-1-4614-1939-6.

F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley Publishing Company, Redwood City, California, xiii + 335 pages (1990).

G. Chartrand, O. R. Oellermann, S. Tian, H. B. Zou and Kalamazoo, Steiner distance in graphs, Casopis Pro Pestování Matematiky 114(4) (1989), 399 – 410, DOI: 10.21136/cpm.1989.118395.

C. J. Colbourn, CRC Handbook of Combinatorial Designs, 1st edition, CRC Press, New York, 784 pages (1996), DOI: 10.1201/9781003040897.

K. L. Collins, A. N. Trenk and R. Whitman, Split graphs and block representations, Discrete Mathematics 347(4) (2024), 113857, DOI: 10.1016/j.disc.2023.113857.

G. Constantine, Lower bounds on the spectra of symmetric matrices with nonnegative entries, Linear Algebra and its Applications 65 (1985), 171 – 178, DOI: 10.1016/0024-3795(85)90095-3.

F. Couto, D. A. Ferraz and S. Klein, New results on edge-coloring and total-coloring of split graphs, Discrete Applied Mathematics 360 (2025), 297 – 306, DOI: 10.1016/j.dam.2024.09.008.

I. Darijani, D. A. Pike and J. Poulin, The chromatic index of block intersection graphs of Kirkman triple systems and cyclic Steiner triple systems, The Australasian Journal of Combinatorics 69(1) (2017), 145 – 158, URL: https://ajc.maths.uq.edu.au/pdf/69/ajc_v69_p145.pdf.

S. Földes and P. L. Hammer, Chapter 6 - Split graphs, Algorithmic Graph Theory and Perfect Graphs 1980 (1980), 149 – 156, DOI: 10.1016/b978-0-12-289260-8.50013-3.

S. Földes and P. L. Hammer, Split graphs having Dilworth number two, Canadian Journal of Mathematics 29(3) (1977), 666 – 672, DOI: 10.4153/CJM-1977-069-1.

K. R. Garren, Bounds for the Eigenvalues of a Matrix, NASA Technical Note, Document ID 19680007865, National Aeronautics and Space Administration, Washington, D.C., USA (1968), URL: https://ntrs.nasa.gov/citations/19680007865.

M. Ghorbani and N. Azimi, Characterization of split graphs with at most four distinct eigenvalues, Discrete Applied Mathematics 184 (2015), 231 – 236, DOI: 10.1016/j.dam.2014.10.039.

F. Goldberg, S. Kirkland, A. Varghese and A. Vijayakumar, On split graphs with four distinct eigenvalues, Discrete Applied Mathematics 277 (2020), 163 – 171, DOI: 10.1016/j.dam.2019.09.016.

L. N. Grippo and V. A. Moyano, On two variants of split graphs: 2-unipolar graph and k-probe-split graph, RAIRO-Operations Research 58(4) (2024), 3597 – 3606, DOI: 10.1051/ro/2023149.

L. Guo and B. L. S. Lin, Vulnerability of super connected split graphs and bisplit graphs, Discrete and Continuous Dynamical Systems – S 12(4&5) (2019), 1179 – 1185, DOI: 10.3934/dcdss.2019081.

M. I. Huilgol and M. D. Vidya, Partially balanced incomplete block (PBIB)-designs associated with geodetic sets in graphs, Discrete Mathematics, Algorithms and Applications 15(1) (2023), 2250059, DOI: 10.1142/S1793830922500598.

S. Li and W. Sun, On split graphs with three or four distinct (normalized) Laplacian eigenvalues, Journal of Combinatorial Designs 28(11) (2020), 763 – 782, DOI: 10.1002/jcd.21743.

R. Merris, Split graphs, European Journal of Combinatorics 24(4) (2003), 413 – 430, DOI: 10.1016/S0195-6698(03)00030-1.

J. W. D. Paola, Block designs and graph theory, Journal of Combinatorial Theory 1(1) (1966), 132 – 148, DOI: 10.1016/S0021-9800(66)80010-8.

G. Sethuraman and M. Nithya, Radio labeling of biconvex split graphs, AKCE International Journal of Graphs and Combinatorics 22(1) (2025), 36 – 42, DOI: 10.1080/09728600.2024.2381712.

G. Song, G. Su and H. Shi, A complete characterization of bidegreed split graphs with four distinct signless Laplacian eigenvalues, Linear Algebra and its Applications 629 (2021), 232 – 245, DOI: 10.1016/j.laa.2021.08.006.

D. R. Stinson, A survey of Kirkman triple systems and related designs, Discrete Mathematics 92(1-3) (1991), 371 – 393, DOI: 10.1016/0012-365X(91)90294-C.

R. I. Tyshkevich and A. A. Chernyak, Canonical partition of a graph defined by the degrees of its vertices, Izvestiya Akademii Nauk SSR, Seriya Fizicheskaya Mathematics 5 (1979), 14 – 26.

H. B. Walikar, B. D. Acharya and S. S. Shirkol, Designs associated with maximum independent sets of a graph, Designs, Codes and Cryptography 57 (2010), 91 – 105, DOI: 10.1007/s10623-009-9351-6.

D. B. West, Introduction to Graph Theory, 2nd edition, Prentice Hall, Upper Saddle River, New Jersey, xi + 314 pages (2001).

H. Wolkowicz and G. P. H. Styan, Bounds for eigenvalues using traces, Linear Algebra and its Applications 29 (1980), 471 – 506, DOI: 10.1016/0024-3795(80)90258-X.

X. Zhan, Extremal eigenvalues of real symmetric matrices with entries in an interval, SIAM Journal of Matrix Analysis and Applications 27(3) (2005), 851 – 860, DOI: 10.1137/050627812.

Downloads

Published

30-11-2024
CITATION

How to Cite

Huilgol, M. I., & Asok, S. (2024). PBIB-Designs and 2-Steiner Distance Eigenvalues of Split Graphs. Communications in Mathematics and Applications, 15(3), 1099–1113. https://doi.org/10.26713/cma.v15i3.2804

Issue

Vol. 15 No. 3 (2024)

Section

Research Article

License

Creative Commons Licence 4.0 by  

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.