A New Spectral Bound on the Clique Number of Graphs

被引：0

作者：

Bulo, Samuel Rota ^{[1
]}

Pelillo, Marcello ^{[1
]}

机构：

[1] Univ Venice, Dipartimento Informat, I-30123 Venice, Italy

来源：

STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION | 2010年 / 6218卷

关键词：

MAXIMAL CLIQUES; ISOMORPHISM; RECOGNITION; ORDER;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Many computer vision and patter recognition problems are intimately related to the maximum clique problem. Due to the intractability of this problem, besides the development of heuristics, a research direction consists in trying to find good bounds on the clique number of graphs. This paper introduces a new spectral upper bound on the clique number of graphs, which is obtained by exploiting an invariance of a continuous characterization of the clique number of graphs introduced by Motzkin and Straus. Experimental results on random graphs show the superiority of our bounds over the standard literature.

引用

页码：680 / 689

页数：10

共 50 条

[41] Lower bounds on the leaf number in graphs with forbidden subgraphs
Mafuta, P.
Mukwembi, S.
Munyira, S.
Rodrigues, B. G.
QUAESTIONES MATHEMATICAE, 2017, 40 (01) : 139 - 149
[42] Bounds on the leaf number in graphs of girth 4 or 5
Mafuta, P.
JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2021, 24 (06) : 1573 - 1582
[43] Total chromatic number of unichord-free graphs
Machado, R. C. S.
de Figueiredo, C. M. H.
DISCRETE APPLIED MATHEMATICS, 2011, 159 (16) : 1851 - 1864
[44] Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number
Corneil, Derek G.
Stacho, Juraj
JOURNAL OF GRAPH THEORY, 2015, 78 (01) : 61 - 79
[45] Spectral solution for detecting isomorphic graphs with nondegenerate eigenvalues
Zahidi, Usman A.
INMIC 2007: PROCEEDINGS OF THE 11TH IEEE INTERNATIONAL MULTITOPIC CONFERENCE, 2007, : 84 - 87
[46] Spectral graph features for the classification of graphs and graph sequences
Schmidt, Miriam
Palm, Guenther
Schwenker, Friedhelm
COMPUTATIONAL STATISTICS, 2014, 29 (1-2) : 65 - 80
[47] On the Number of Fixed Points of Automorphisms of Vertex-Transitive Graphs
Potocnik, Primoz
Spiga, Pablo
COMBINATORICA, 2021, 41 (05) : 703 - 747
[48] The number and average size of connected sets in graphs with degree constraints
Haslegrave, John
JOURNAL OF GRAPH THEORY, 2022, 100 (03) : 530 - 542
[49] Degree Associated Reconstruction Number of Graphs with Regular Pruned Graph
Devi, P. Anusha
Monikandan, S.
ARS COMBINATORIA, 2017, 134 : 29 - 41
[50] Equality in a bound that relates the size and the restrained domination number of a graph
Hattingh, Johannes H.
Joubert, Ernst J.
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (04) : 1586 - 1608

← 1 2 3 4 5 →