Spectra of closeness Laplacian and closeness signless Laplacian of graphs

Zheng, Lu; Zhou, Bo

doi:10.1051/ro/2022161

Zheng, Lu ; Zhou, Bo

RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3525-3543

Résumé

For a graph G with vertex set V(G) and u, v ∈ V(G), the distance between vertices u and v in G, denoted by d$$(u,v), is the length of a shortest path connecting them and it is ∞ if there is no such a path, and the closeness of vertex u in G is $c_{G} (u) = \sum_{w} 2^{- d_{G} (u, w)}$ . Given a graph G that is not necessarily connected, for u, v∈V(G), the closeness matrix of G is the matrix whose (u,v)-entry is equal to $2^{- d_{G} (u, v)}$ if u≠v and 0 otherwise, the closeness Laplacian is the matrix whose (u,v)-entry is equal to

\{\begin{matrix} - 2^{- d_{G} (u, v)} if u \neq v, \\ c_{G} (u) otherwise \end{matrix}

and the closeness signless Laplacian is the matrix whose (u,v)-entry is equal to

\{\begin{matrix} 2^{- d_{G} (u, v)} & if u \neq v, \\ c_{G} (u) otherwise . \end{matrix}

We establish relations connecting the spectral properties of closeness Laplacian and closeness signless Laplacian and the structural properties of graphs. We give tight upper bounds for all nontrivial closeness Laplacian eigenvalues and characterize the extremal graphs, and determine all trees and unicyclic graphs that maximize the second smallest closeness Laplacian eigenvalue. Also, we give tight upper bounds for the closeness signless Laplacian eigenvalues and determine the trees whose largest closeness signless Laplacian eigenvalues achieve the first two largest values.

MR Zbl

DOI : 10.1051/ro/2022161

Classification : 05C50, 15A42, 15C35
Keywords: Closeness Laplacian spectrum, closeness signless Laplacian spectrum, distances in graphs, extremal graphs

@article{RO_2022__56_5_3525_0,
     author = {Zheng, Lu and Zhou, Bo},
     title = {Spectra of closeness {Laplacian} and closeness signless {Laplacian} of graphs},
     journal = {RAIRO. Operations Research},
     pages = {3525--3543},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {5},
     doi = {10.1051/ro/2022161},
     mrnumber = {4498602},
     zbl = {1502.05151},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022161/}
}

TY  - JOUR
AU  - Zheng, Lu
AU  - Zhou, Bo
TI  - Spectra of closeness Laplacian and closeness signless Laplacian of graphs
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 3525
EP  - 3543
VL  - 56
IS  - 5
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022161/
DO  - 10.1051/ro/2022161
LA  - en
ID  - RO_2022__56_5_3525_0
ER  -

%0 Journal Article
%A Zheng, Lu
%A Zhou, Bo
%T Spectra of closeness Laplacian and closeness signless Laplacian of graphs
%J RAIRO. Operations Research
%D 2022
%P 3525-3543
%V 56
%N 5
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022161/
%R 10.1051/ro/2022161
%G en
%F RO_2022__56_5_3525_0

Zheng, Lu; Zhou, Bo. Spectra of closeness Laplacian and closeness signless Laplacian of graphs. RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3525-3543. doi: 10.1051/ro/2022161

Bibliographie
Cité par

L. Zheng and B. Zhou, On the spectral closeness and residual spectral closeness of graphs. RAIRO: OR 56 (2022) 2651–2668. | MR | Zbl | Numdam | DOI

R. B. Bapat, A. K. Lal and S. Pati, A $q$ -analogue of the distance matrix of a tree. Linear Algebra Appl. 416 (2006) 799–814. | MR | Zbl | DOI

W. Yan and Y.-N. Yeh, The determinants of $q$ -distance matrices of trees and two quantities relating to permutations. Adv. Appl. Math. 39 (2007) 311–321. | MR | Zbl | DOI

C. Dangalchev, Residual closeness in networks. Phys. A 365 (2006) 556–564. | DOI

C. Dangalchev, Residual closeness and generalized closeness. Internat. J. Found. Comput. Sci. 22 (2011) 1939–1948. | MR | Zbl | DOI

D. Rupnik Poklukar and J. Žerovnik, Networks with extremal closeness. Fund. Inform. 167 (2019) 219–234. | MR | Zbl

A. Aytaç and Z. N. Odabaş, Robustness of regular caterpillars. Internat. J. Found. Comput. Sci. 28 (2017) 835–841. | MR | Zbl | DOI

H. Hosoya, On some counting polynomials in chemistry. Discrete Appl. Math. 19 (1988) 239–257. | MR | Zbl | DOI

L. Zheng and B. Zhou, The closeness spectral properties of graphs. Preprint

S. Butler, E. Cooper, A. Li, K. Lorenzen and Z. Schopick, Spectral properties of the exponential distance matrix. Preprint (2019). | arXiv | MR | Zbl

K. J. Lorenzen, Cospectral Constructions and Spectral Properties of Variations of the Distance Matrix. Ph.D. thesis, Iowa State University, USA (2021). | MR | DOI

M. Aouchiche and P. Hansen, Two Laplacians for the distance matrix of a graph. Linear Algebra Appl. 439 (2013) 21–33. | MR | Zbl | DOI

R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed.. Cambridge University Press, Cambridge (2013). | MR | Zbl

A. Brouwer and W. Haemers, Spectra of Graphs. Springer, New York (2012). | MR | Zbl | DOI

H. Guo and B. Zhou, Minimum status of trees with a given degree sequence. Acta Inform. (2022) . | DOI | MR | Zbl

D. Vukičević and G. Caporossi, Network descriptors based on betweenness centrality and transmission and their extremal values. Discrete Appl. Math. 161 (2013) 2678–2686. | MR | Zbl | DOI

V. Nikiforov, Merging the A- and Q-spectral theories. Appl. Anal. Discrete Math. 11 (2017) 81–107. | MR | Zbl | DOI

Cité par Sources :