PBIB-Designs and 2-Steiner distance eigenvalues of split graphs
PBIB-Designs and 2-Steiner distance eigenvalues of split graphs
Keywords:
PBIB-design, Split graph, Steiner distance matrix, SpectrumAbstract
In this paper, we have considered split graph Kn XK1 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 XK1. 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 XK1. Furthermore, we have
given interlacing for adjacency, distance and 2-Steiner distance spectra of split graph Kn XK1. Time
complexity and algorithm for finding rank of a matrix is given. A conjecture concludes the paper.
Downloads
References
References
A. Azimi, R. B. Bapat and S. Goel, Steiner distance matrix of caterpillar graphs, Special Matrices
(2022), 267 – 284, doi:10.1515/spma-2022-0162.
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.
P. Bhunia, K. Paul and S. Bag, Bounds for eigenvalues of the adjacency matrix of a graph, Journal
of Interdisciplinary Mathematics (2019), 1 – 17, doi:10.1080/09720502.2019.1630938.
R. C. Bose and K. R. Nair, Partially balanced incomplete block designs, Sankhya. 4(3) (1939), 337
– 372.
A. E. Brouwer and W. H. Haemers, Spectra of graphs, Springer, New York (2012),
doi:10.1007/978-1-4614-1939-6.
F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, Boston (1990).
G. Chartrand, O. R. Oellermann, S. Tian, H. B. Zou and Kalamazoo, Steiner distance in graphs,
Casopis Pro Pestovani Matematiky 4 (1989) 399 – 410.
C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, 2nd edition, CRC Press,
Boca Raton (2007).
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.
J. Cooper and Z. Du, Note on the spectra of Steiner distance hypermatrices, arXiv:2403.02287v1
(2024), doi:10.48550/arXiv.2403.02287.
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.
S. Foldes and P. L. Hammer, Split graphs, Congressus Numerantium 19 (1977), 311 – 315.
S. Foldes and P. L. Hammer, Split graphs having Dilworth number two, Canadian Journal of Mathematics
(3) (1977), 666 – 672, doi:10.4153/CJM-1977-069-1.
K. R. Garren, Bounds for the eigenvalues of a matrix, NASA Technical Note, Washington D. C.
(1968).
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.
M. I. Huilgol and M. D. Vidya, Partially balanced incomplete block (PBIB)- designs arising from
geodetic sets in graphs, Discrete Mathematics, Algorithms and Applications 15(1) (2023), 2250059
– 2250076, doi:10.1142/S1793830922500598.
Y. Mao, Steiner Distance in Graphs - A Survey, arXiv:1708.05779v1 (2017),
doi:10.48550/arXiv.1708.05779.
R. Merris, Split graphs, European Journal of Combinatorics 24 (2003), 413 – 430,
doi:10.1016/S0195-6698(03)00030-1.
J. W. Di Paola, Block Designs and Graph Theory, Journal of Combinatorial Theory 1 (1966), 132
– 148, doi:10.1016/S0021-9800(66)80010-8.
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.
G. Su, G. Song, J. Yin and J. Du, A complete characterization of Bidegreed split graphs with four
distinct - eigenvalues, Symmetry. 14 (2022), 899, doi:10.3390/sym14050899.
R. I. Tyshkevich and A. A. Chernyak, Canonical partition of a graph defined by the degrees of its
vertices, Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk. 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 (2007), 91 – 105, doi:10.1007/s10623-009-
-6.
D. B. West, Introduction to Graph Theory,Upper Saddle River, New Jersey Prentice Hall (1996).
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 J.
Matrix Anal. Appl. 27 (3) (2006), 851 – 860, doi:10.1137/050627812.
Published
How to Cite
Issue
Section
License
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.
