Top

Journal of Combinatorial Optimization

Published in:

24-05-2019

The spectral radius and domination number in linear uniform hypergraphs

Authors: Liying Kang, Wei Zhang, Erfang Shan

Published in: Journal of Combinatorial Optimization | Issue 3/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper investigates the spectral radius and signless Laplacian spectral radius of linear uniform hypergraphs. A dominating set in a hypergraph H is a subset D of vertices if for every vertex v not in D there exists \(u\in D\) such that u and v are contained in a hyperedge of H. The minimum cardinality of a dominating set of H is called the domination number of H. We present lower bounds on the spectral radius and signless Laplacian spectral radius of a linear uniform hypergraph in terms of its domination number.

previous article Improved algorithms for single vehicle scheduling on tree/cycle networks

next article Big data driven urban railway planning: Shenzhen metro case study

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Acharya BD (2007) Domination in hypergraphs. AKCE J Comb 4:117–126MathSciNetMATH

Aouchiche M, Hansen P, Stevanović D (2010) A sharp upper bound on algebraic connectivity using domination number. Linear Algebra Appl 432:2879–2893MathSciNetCrossRef

Brand C, Seifter N (1996) Eigenvalues and domination in graphs. Math Slov 46:33–39MathSciNetMATH

Bujtás C, Henning MA, Tuza Z (2012) Transversals and domination in uniform hypergraphs. Eur J Comb 33:62–71MathSciNetCrossRef

Chang K, Pearson K, Zhang T (2008) Perron–Frobenius theorem for nonegative tensors. Commun Math Sci 6:507–520MathSciNetCrossRef

Chang K, Qi L, Zhang T (2013) A survey on the spectral theory of nonnegative tensors. Numer Linear Algebra Appl 20:891–912MathSciNetCrossRef

Cooper J, Dutle A (2012) Spectra of uniform hypergraphs. Linear Algebra Appl 436:3268–3292MathSciNetCrossRef

Friedland S, Gaubert A, Han L (2013) Perron–Frobenius theorems for nonnegative multilinear forms and extensions. Linear Algebra Appl 438:738–749MathSciNetCrossRef

Har J (2014) A note on Laplacian eigenvalues and domination. Linear Algebra Appl 449:115–118MathSciNetCrossRef

Haynes TW, Hedetniemi ST, Slater PJ (1998a) Fundamentals of domination in graphs. Marcel Dekker Inc., New YorkMATH

Haynes TW, Hedetniemi ST, Slater PJ (1998b) Domination in graphs: advanced topics. Marcel Dekker Inc., New YorkMATH

Henning MA, Löwenstein C (2012) Hypergraphs with large domination number and edge sizes at least 3. Discrete Appl Math 160:1757–1765MathSciNetCrossRef

Henning MA, Yeo A (2013) Total domination in graphs. Springer, New YorkCrossRef

Hu S, Qi L, Shao J (2013) Cored hypergraphs, power hypergraphs and their Laplacian \(H\)-eigenvalues. Linear Algebra Appl 439:2980–2998MathSciNetCrossRef

Hu S, Qi L, Xie J (2015) The largest Laplacian and signless Laplacian \(H\)-eigenvalues of a uniform hypergraph. Linear Algebra Appl 469:1–27MathSciNetCrossRef

Jose BK, Tuza Zs (2009) Hypergraph domination and strong independence. Appl Anal Discrete Math 3:237–358MathSciNetCrossRef

Kang L, Li S, Dong Y, Shan E (2017) Matching and domination numbers in \(r\)-uniform hypergraphs. J Comb Optim 34:656–659MathSciNetCrossRef

Lim LH (2005) Singular values and eigenvalues of tensors: a variational approach. In: Proceedings of the IEEE international workshop on computational advances in multi-sensor adaptive processing, vol 1. CAMSAP’05, pp 129–132

Lu L, Man S (2016) Connected hypergraphs with small spectral radius. Linear Algebra Appl 508:206–227MathSciNetCrossRef

Nikiforov V (2007) Bounds on graph eignvalues I. Linear Algebra Appl 420:667–671MathSciNetCrossRef

Qi L (2005) Eigenvalues of a real supersymmetric tensor. J Symb Comput 40:1302–1324MathSciNetCrossRef

Shao J (2013) A general product of tensors with applications. Linear Algebra Appl 439:2350–2366MathSciNetCrossRef

Xing R, Zhou B (2015) Laplacian and signless Laplacian spectral radii of graphs with fixed domination number. Math Nachr 188:476–480MathSciNetCrossRef

Yang Y, Yang Q (2010) Further results for Perron–Frobenius theorem for nonnegative tensors. SIAM J Matrix Anal Appl 31:2517–2530MathSciNetCrossRef

Yang Y, Yang Q (2011) On some properties of nonegative weakly irreducible tensors. arXiv:1111.0713v2

Zhou J, Sun L, Wang W, Bu C (2014) Some spectral properties of uniform hypergraphs. Electron J Comb 21:#P4.24MathSciNetCrossRef

Title: The spectral radius and domination number in linear uniform hypergraphs
Authors: Liying Kang
Wei Zhang
Erfang Shan
Publication date: 24-05-2019
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2021
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00424-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2021

An improved algorithm for the -MaxSAT problem: asking branchings to satisfy the clauses

Preface: special issue on the annual international conference on combinatorial optimization and applications (COCOA)

Improved algorithms for single vehicle scheduling on tree/cycle networks

On the complexity of and algorithms for detecting k-length negative cost cycles

Algorithms for the metric ring star problem with fixed edge-cost ratio

Modified Greedy Heuristic for the one-dimensional cutting stock problem

Premium Partner