Results 1 to 10 of about 8,766 (207)
A local core number based algorithm for the maximum clique problem [PDF]
Transactions on Combinatorics, 2021 The maximum clique problem (MCP) is to determine a complete subgraph of maximum cardinality in a graph. MCP is a fundamental problem in combinatorial optimization and is noticeable for its wide range of applications.
Neda Mohammadi, Mehdi Kadivar
doaj +2 more sources
The Smallest Spectral Radius of Graphs with a Given Clique Number [PDF]
The Scientific World Journal, 2014 The first four smallest values of the spectral radius among all connected graphs with maximum clique size ω≥2 are obtained.
Jing-Ming Zhang +2 more
doaj +2 more sources
On clique‐inverse graphs of graphs with bounded clique number [PDF]
Journal of Graph Theory, 2020 AbstractThe clique graph K(G) of G is the intersection graph of the family of maximal cliques of G. For a family of graphs, the family of clique‐inverse graphs of , denoted by , is defined as . Let be the family of Kp‐free graphs, that is, graphs with clique number at most p − 1, for an integer constant p ≥ 2.
Liliana Alcón +4 more
openaire +4 more sources
Exact square coloring of graphs resulting from some graph operations and products
AKCE International Journal of Graphs and Combinatorics, 2022 A vertex coloring of a graph [Formula: see text] is called an exact square coloring of G if any pair of vertices at distance 2 receive distinct colors.
Priyamvada, B. S. Panda
doaj +1 more source
Squares of Low Clique Number [PDF]
Electronic Notes in Discrete Mathematics, 2016 The Square Root problem is that of deciding whether a given graph admits a square root. This problem is only known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number of other graph classes.
Golovach, Petr +3 more
openaire +4 more sources
Some Extremal Graphs with Respect to Sombor Index
Mathematics, 2021 Let G be a graph with set of vertices V(G)(|V(G)|=n) and edge set E(G). Very recently, a new degree-based molecular structure descriptor, called Sombor index is denoted by SO(G) and is defined as SO=SO(G)=∑vivj∈E(G)dG(vi)2+dG(vj)2, where dG(vi) is the ...
Kinkar Chandra Das, Yilun Shang
doaj +1 more source
Properties of SuperHyperGraph and Neutrosophic SuperHyperGraph [PDF]
Neutrosophic Sets and Systems, 2022 New setting is introduced to study dominating, resolving, coloring, Eulerian(Hamiltonian) neutrosophic path, n-Eulerian(Hamiltonian) neutrosophic path, zero forcing number, zero forcing neutrosophicnumber, independent number, independent neutrosophic ...
Henry Garrett
doaj +1 more source
Tight Bounds on the Clique Chromatic Number [PDF]
The Electronic Journal of Combinatorics, 2021 The clique chromatic number of a graph is the minimum number of colours needed to colour its vertices so that no inclusion-wise maximal clique which is not an isolated vertex is monochromatic. We show that every graph of maximum degree $\Delta$ has clique chromatic number $O\left(\frac{\Delta}{\log~\Delta}\right)$.
Joret, Gwenaël +3 more
openaire +4 more sources
Fast Diameter Computation within Split Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 When can we compute the diameter of a graph in quasi linear time? We address this question for the class of {\em split graphs}, that we observe to be the hardest instances for deciding whether the diameter is at most two.
Guillaume Ducoffe +2 more
doaj +1 more source
A Note on the Signed Clique Domination Numbers of Graphs
Journal of Mathematics, 2022 Let G=V,E be a graph. A function f:E⟶−1,+1 is said to be a signed clique dominating function (SCDF) of G if ∑e∈EKfe≥1 holds for every nontrivial clique K in G. The signed clique domination number of G is defined as γscl′G=min∑e∈EGfe|fis an SCDF ofG.
Baogen Xu, Ting Lan, Mengmeng Zheng
doaj +1 more source