Results 21 to 30 of about 8,457 (169)
Local and Global Clique Numbers
Journal of Combinatorial Theory, Series B, 1994 A graph \(G\) is said to have the \((p,q)\)-property for some integers \(p\geq q\geq 2\) if for every \(p\)-set of its vertices the induced subgraph contains a \(q\)-clique. The aim of the paper is to investigate relations of the type \((p,q)\to (n,s)\), meaning that each graph having the \((p,q)\)- property also has the \((n,s)\)-property.
Linial, N., Rabinovich, Y.
openaire +2 more sources
Minimum Clique Number, Chromatic Number, and Ramsey Numbers [PDF]
The Electronic Journal of Combinatorics, 2012 Let $Q(n,c)$ denote the minimum clique number over graphs with $n$ vertices and chromatic number $c$. We investigate the asymptotics of $Q(n,c)$ when $n/c$ is held constant. We show that when $n/c$ is an integer $\alpha$, $Q(n,c)$ has the same growth order as the inverse function of the Ramsey number $R(\alpha+1,t)$ (as a function of $t$). Furthermore,
openaire +2 more sources
Connected Domination Number and a New Invariant in Graphs with Independence Number Three [PDF]
Computer Science Journal of Moldova, 2021 Adding a connected dominating set of vertices to a graph $G$ increases its number of Hadwiger $h(G)$. Based on this obvious property in [2] we introduced a new invariant $\eta(G)$ for which $\eta(G)\leq h(G)$. We continue to study its property.
Vladimir Bercov
doaj
On a class of polynomials associated with the Cliques in a graph and its applications
International Journal of Mathematics and Mathematical Sciences, 1989 The clique polynomial of a graph is defined. An explicit formula is then derived for the clique polynomial of the complete graph. A fundamental theorem and a reduction process is then given for clique polynomials.
E. J. Farrell
doaj +1 more source
Hard optimization problems have soft edges
Scientific Reports, 2023 Finding a Maximum Clique is a classic property test from graph theory; find any one of the largest complete subgraphs in an Erdös-Rényi G(N, p) random graph. We use Maximum Clique to explore the structure of the problem as a function of N, the graph size,
Raffaele Marino, Scott Kirkpatrick
doaj +1 more source
Discrete Mathematics, 1986 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Erdös, Paul, Erné, Marcel
openaire +1 more source
Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
Algorithms, 2021 This paper studies the maximum-clique independence problem and some variations of the clique transversal problem such as the {k}-clique, maximum-clique, minus clique, signed clique, and k-fold clique transversal problems from algorithmic aspects for k ...
Chuan-Min Lee
doaj +1 more source
An optimization algorithm for maximum quasi-clique problem based on information feedback model [PDF]
PeerJ Computer ScienceThe maximum clique problem in graph theory is a well-known challenge that involves identifying the complete subgraph with the highest number of nodes in a given graph, which is a problem that is hard for nondeterministic polynomial time (NP-hard problem).
Shuhong Liu +4 more
doaj +2 more sources
JTAM (Jurnal Teori dan Aplikasi Matematika), 2023 Graph theory can give a representation of abstract mathematical systems such as groups or rings. We have many graph representations for a group, in this study we use the coprime graph representation for a generalized quaternion group to find the ...
Marena Rahayu Gayatri +5 more
doaj +1 more source
Chromatic and clique numbers of a class of perfect graphs [PDF]
Transactions on Combinatorics, 2015 Let p be a prime number and n be a positive integer. The graph G p (n) is a graph with vertex set [n]=1,2,ldots,n , in which there is an arc from u to v if and only if uneqv and pnmidu+v . In this paper it is shown that G p (n) is a perfect
Mohammad Reza Fander
doaj