Geodesic
Spectral Conditions for Graphs to be k-Hamiltonian or k-Path-Coverable
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 161-179.

Voir la notice de l'article provenant de la source Library of Science

A graph G is k-Hamiltonian if for all X ⊂ V (G) with |X| ≤ k, the subgraph induced by V (G) X is Hamiltonian. A graph G is k-path-coverable if V (G) can be covered by k or fewer vertex disjoint paths. In this paper, by making use of the vertex degree sequence and an appropriate closure concept (due to Bondy and Chvátal), we present sufficient spectral conditions of a connected graph with fixed minimum degree and large order to be k-Hamiltonian or k-path-coverable.
Keywords: spectral radius, minimum degree, k -Hamiltonian, k -path-coverable 
@article{DMGT_2020_40_1_a10,
     author = {Liu, Weijun and Liu, Minmin and Zhang, Pengli and Feng, Lihua},
     title = {Spectral {Conditions} for {Graphs} to be {k-Hamiltonian} or {k-Path-Coverable}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {161--179},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a10/}
}
TY  - JOUR
AU  - Liu, Weijun
AU  - Liu, Minmin
AU  - Zhang, Pengli
AU  - Feng, Lihua
TI  - Spectral Conditions for Graphs to be k-Hamiltonian or k-Path-Coverable
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 161
EP  - 179
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a10/
LA  - en
ID  - DMGT_2020_40_1_a10
ER  - 
%0 Journal Article
%A Liu, Weijun
%A Liu, Minmin
%A Zhang, Pengli
%A Feng, Lihua
%T Spectral Conditions for Graphs to be k-Hamiltonian or k-Path-Coverable
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 161-179
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a10/
%G en
%F DMGT_2020_40_1_a10
Liu, Weijun; Liu, Minmin; Zhang, Pengli; Feng, Lihua. Spectral Conditions for Graphs to be k-Hamiltonian or k-Path-Coverable. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 161-179. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a10/

[1] D. Bauer, H.J. Broersma, J. van den Heuvel, N. Kahl, A. Nevo, E. Schmeichel, D.R. Woodall and M. Yatauro, Best monotone degree conditions for graph properties: a survey, Graphs Combin. 31 (2015) 1–22. doi:10.1007/s00373-014-1465-6

[2] J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111–135. doi:10.1016/0012-365X(76)90078-9

[3] R.A. Brualdi and E.S. Solheid, On the spectral radius of complementary acyclic matrices of zeros and ones, SIAM J. Alg. Discrete Meth. 7 (1986) 265–272. doi:10.1137/0607030

[4] L. Chen, J. Liu and Y. Shi, Matching energy of unicyclic and bicyclic graphs with a given diameter, Complexity 21 (2015) 224–238. doi:10.1002/cplx.21599

[5] V. Chvátal, On Hamiltons ideals, J. Combin. Theory Ser. B 12 (1972) 163–168. doi:10.1016/0095-8956(72)90020-2

[6] G. Chartrand, S. Kapoor and D. Lick, n-Hamiltonian graphs, J. Combin. Theory 9 (1970) 308–312. doi:10.1016/S0021-9800(70)80069-2

[7] L.H. Feng, P.L. Zhang, H. Liu, W. Liu, M. Liu and Y. Hu, Spectral conditions for some graphical properties, Linear Algebra Appl. 524 (2017) 182–198. doi:10.1016/j.laa.2017.03.006

[8] L.H. Feng, G. Yu and X.-D. Zhang, Spectral radius of graphs with given matching number, Linear Algebra Appl. 422 (2007) 133–138. doi:10.1016/j.laa.2006.09.014

[9] L.H. Feng, J. Cao, W. Liu, S. Ding and H. Liu, The spectral radius of edge chromatic critical graphs, Linear Algebra Appl. 492 (2016) 78–88. doi:10.1016/j.laa.2015.11.019

[10] L.H. Feng, P. Zhang and W. Liu, Spectral radius and k-connectedness of a graph, Monatsh. Math. 185 (2018) 651–661. doi:10.1007/s00605-017-1055-9

[11] L.H. Feng, X. Zhu and W. Liu, Wiener index, Harary index and graph properties, Discrete Appl. Math. 223 (2017) 72–83. doi:10.1016/j.dam.2017.01.028

[12] M. Fiedler and V. Nikiforov, Spectral radius and Hamiltonicity of graphs, Linear Algebra Appl. 432 (2010) 2170–2173. doi:10.1016/j.laa.2009.01.005

[13] P. Hansen and D. Stevanović, On bags and bugs, Discrete Appl. Math. 156 (2008) 986–997. doi:10.1016/j.dam.2007.05.044

[14] Y. Hong, J.L Shu and K. Fang, A sharp upper bound of the spectral radius of graphs, J. Combin. Theory Ser. B 81 (2001) 177–183. doi:10.1006/jctb.2000.1997

[15] B. Huo, X. Li and Y. Shi, Complete solution to a conjecture on the maximal energy of unicyclic graphs, European J. Combin. 32 (2011) 662–673. doi:10.1016/j.ejc.2011.02.011

[16] L. Lesniak, On n-Hamiltonian graphs, Discrete Math. 14 (1976) 165–169. doi:10.1016/0012-365X(76)90059-5

[17] B. Li and B. Ning, Spectral analogues of Erdős ’ and Moon-Moser ’ s theorems on Hamilton cycles, Linear Multilinear Algebra 64 (2016) 2252–2269. doi:10.1080/03081087.2016.1151854

[18] H. Li, Generalizations of Dirac ’ s theorem in Hamiltonian graph theory — A survey, Discrete Math. 313 (2013) 2034–2053. doi:10.1016/j.disc.2012.11.025

[19] J. Li and G. Steiner, Partitioning a graph into vertex-disjoint paths, Studia Sci. Math. Hungar. 42 (2005) 277–294. doi:10.1556/SScMath.42.2005.3.3

[20] S. Li and X. Li, On tricyclic graphs of a given diamater with minimal energy, Linear Algebra Appl. 430 (2009) 370–385. doi:10.1016/j.laa.2008.08.004

[21] S.C. Li and N. Li, On minimal energies of trees with given diameter, Electron. J. Linear Algebra 17 (2008) 414–425. doi:10.13001/1081-3810.1272

[22] X. Li, M. Wei, J. Li and Y. Shi, On a conjecture about tricyclic graphs with maximal energy, MATCH Commun. Math. Comput. Chem. 72 (2014) 183–214.

[23] Y. Li, Y. Liu and X. Peng, Signless Laplacian spectral radius and Hamiltonicity of graphs with large minimum degree, Linear Multilinear Algebra (2017), in press. doi:10.1080/03081087.2017.1383346

[24] R. Liu, W.C. Shiu and J. Xue, Sufficient spectral conditions on Hamiltonian and traceable graphs, Linear Algebra Appl. 467 (2015) 254–266. doi:10.1016/j.laa.2014.11.017

[25] W. Liu, M. Liu and L. Feng, Spectral conditions for graphs to be β-deficient involving minimum degree, Linear Multilinear Algebra 66 (2018) 792–802. doi:10.1080/03081087.2017.1323845

[26] M. Lu, H. Liu and F. Tian, Spectral radius and Hamiltonian graphs, Linear Algebra Appl. 437 (2012) 1670–1674. doi:10.1016/j.laa.2012.05.021

[27] V. Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl. 432 (2010) 2243–2256. doi:10.1016/j.laa.2009.05.023

[28] V. Nikiforov, Spectral radius and Hamiltonicity of graphs with large minimum degree, Czechoslovak Math. J. 66 (141) (2016) 925–940. doi:10.1007/s10587-016-0301-y

[29] V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2002) 179–189. doi:10.1017/S0963548301004928

[30] B. Ning and J. Ge, Spectral radius and Hamiltonian properties of graphs, Linear Multilinear Algebra 63 (2015) 1520–1530. doi:10.1080/03081087.2014.947984

[31] B. Ning and B. Li, Spectral radius and traceability of connected claw-free graphs, Filomat 30 (2016) 2445–2452. doi:10.2298/FIL1609445N

[32] D. Stevanović, M. Aouchiche and P. Hansen, On the spectral radius of graphs with a given domination number, Linear Algebra Appl. 428 (2008) 1854–1864. doi:10.1016/j.laa.2007.10.024

[33] D. Stevanović, Spectral Radius of Graphs (Academic Press, Amsterdam, 2015).

[34] G.H. Yu, L.H. Feng, A. Ilić and D. Stevanović, The signless Laplacian spectral radius of bounded degree graphs on surfaces, Appl. Anal. Discrete Math. 9 (2015) 332–346. doi:10.2298/AADM150722015Y

[35] G.D. Yu and Y.Z. Fan, Spectral conditions for a graph to be Hamilton-connected, Appl. Mechanics Materials 336-338 (2013) 2329–2334. doi:10.4028/www.scientific.net/AMM.336-338.2329

[36] M. Zhang and S.C. Li, Extremal Halin graphs with respect to the signless Laplacian spectra, Discrete Appl. Math. 213 (2016) 207–218. doi:10.1016/j.dam.2016.05.020

[37] M. Zhang and S.C. Li, Extremal cacti of given matching number with respect to the distance spectral radius, Appl. Math. Comput. 291 (2016) 89–97. doi:10.1016/j.amc.2016.06.031

[38] B. Zhou, Signless Laplacian spectral radius and Hamiltonicity, Linear Algebra Appl. 432 (2010) 566–570. doi:10.1016/j.laa.2009.09.004

[39] Q. Zhou and L. Wang, Some sufficient spectral conditions on Hamilton-connected and traceable graphs, Linear Multilinear Algebra 65 (2017) 224–234. doi:10.1080/03081087.2016.1182463

[40] Q.N. Zhou and L.G. Wang, Distance signless Laplacian spectral radius and Hamiltonian properties of graphs, Linear Multilinear Algebra 65 (2017) 2316–2323. doi:10.1080/03081087.2016.1273314

[41] Q.N. Zhou, L.G. Wang and Y. Lu, Wiener-type invariants on graph properties, Filomat 32 (2018) 489–502. doi:10.2298/FIL1802489Z

[42] Q.N. Zhou, L.G. Wang and Y. Lu, Some sufficient conditions on k-connected graphs, Appl. Math. Comput. 325 (2018) 332–339. doi:10.1016/j.amc.2017.12.043