Results 31 to 40 of about 1,967 (126)

Independent Set Reconfiguration in Cographs [PDF]

, 2014
We study the following independent set reconfiguration problem, called TAR-Reachability: given two independent sets $I$ and $J$ of a graph $G$, both of size at least $k$, is it possible to transform $I$ into $J$ by adding and removing vertices one-by-one,
AE Mouawad, B Courcelle, C Eggermont, D Corneil, F Gavril, GJ Minty, J Heuvel van den, K Vušković, L Cereceda, L Cereceda, L Cereceda, M Bonamy, M Kamiński, M Kamiński, N Sbihi, P Bonsma, P Bonsma, P Bonsma, P Gopalan, RA Hearn, T Ito, T Ito   +21 more
core   +2 more sources

Polar cographs

Discrete Applied Mathematics, 2007
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Ekim, T., Mahadev, N.V.R., de Werra, D.
openaire   +2 more sources

$2$-polarity and algorithmic aspects of polarity variants on cograph superclasses [PDF]

Discrete Mathematics & Theoretical Computer Science
A graph $G$ is said to be an $(s, k)$-polar graph if its vertex set admits a partition $(A, B)$ such that $A$ and $B$ induce, respectively, a complete $s$-partite graph and the disjoint union of at most $k$ complete graphs.
Fernando Esteban Contreras-Mendoza, César Hernández-Cruz   +1 more
doaj   +1 more source

On perfect and quasiperfect dominations in graphs [PDF]

, 2017
A subset S ¿ V in a graph G = ( V , E ) is a k -quasiperfect dominating set (for k = 1) if every vertex not in S is adjacent to at least one and at most k vertices in S .
Cáceres, José, Hernando Martín, María del Carmen, Mora Giné, Mercè, Pelayo Melero, Ignacio Manuel, Puertas, M. Luz   +4 more
core   +2 more sources

Characterization of Graphs with an Eigenvalue of Large Multiplicity

Advances in Mathematical Physics, Volume 2020, Issue 1, 2020., 2020
Let G be a simple and undirected graph. The eigenvalues of the adjacency matrix of G are called the eigenvalues of G. In this paper, we characterize all the n‐vertex graphs with some eigenvalue of multiplicity n − 2 and n − 3, respectively. Moreover, as an application of the main result, we present a family of nonregular graphs with four distinct ...
Linming Qi, Lianying Miao, Weiliang Zhao, Lu Liu, Pavel Kurasov   +4 more
wiley   +1 more source

Forbidden subgraphs of Co-prime graphs of finite groups [PDF]

Transactions on Combinatorics
For a finite group $G$ the co-prime graph $\Gamma(G)$ is defined as a graph with vertex set $G$ in which two distinct vertices $x$ and $y$ are adjacent if and only if $gcd(o(x),o(y))=1$ where $o(x)$ and $o(y)$ denote the orders of the elements $x$ and $y$
Swathi V V, M. S. Sunitha
doaj   +1 more source

Cographs: Eigenvalues and Dilworth number [PDF]

Discrete Mathematics, 2019
13 pages, Comments from referees ...
openaire   +3 more sources

Characterizing and computing minimal cograph completions [PDF]

Discrete Applied Mathematics, 2008
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Papadopoulos, C., Lokshtanov, D., Mancini, F.   +2 more
openaire   +2 more sources

Finite groups whose coprime graph is split, threshold, chordal, or a cograph [PDF]

Proceedings of the Estonian Academy of Sciences
Given a finite group G, the coprime graph of G, denoted by Γ(G), is defined as an undirected graph with the vertex set G, and for distinct x, y ∈ G, x is adjacent to y if and only if (o(x), o(y)) = 1, where o(x) and o(y) are the orders of x and y ...
Jin Chen, Shixun Lin, Xuanlong Ma
doaj   +1 more source

Families of Integral Cographs within a Triangular Array

Special Matrices, 2020
The determinant Hosoya triangle, is a triangular array where the entries are the determinants of two-by-two Fibonacci matrices. The determinant Hosoya triangle mod 2 gives rise to three infinite families of graphs, that are formed by complete product ...
Ching Hsin-Yun, Flórez Rigoberto, Mukherjee Antara   +2 more
doaj   +1 more source