Results 1 to 10 of about 438 (125)
Apex Graphs and Cographs [PDF]
Theory and Applications of Graphs, 2023 11 pp., 7 figures; v2 writing and figures slightly ...
Jagdeep Singh +2 more
openalex +6 more sources
On Rödl's Theorem for Cographs [PDF]
The Electronic Journal of Combinatorics, 2023 A theorem of Rödl states that for every fixed $F$ and $\varepsilon>0$ there is $\delta=\delta_F(\varepsilon)$ so that every induced $F$-free graph contains a vertex set of size $\delta n$ whose edge density is either at most $\varepsilon$ or at least $1-\varepsilon$.
Lior Gishboliner, A. Shapira
openalex +2 more sources
The Micro-world of Cographs [PDF]
Combinatorial Algorithms31st International Workshop, 2020 Cographs constitute a small point in the atlas of graph classes. However, by zooming in on this point, we discover a complex world, where many parameters jump from finiteness to infinity. In the present paper, we identify several milestones in the world of cographs and create a hierarchy of graph parameters grounded on these milestones.
Alecu B, Lozin V, de Werra D.
europepmc +4 more sources
Generalizing Cographs to 2-Cographs [PDF]
The Electronic Journal of Combinatorics, 2023 A graph in which every connected induced subgraph has a disconnected complement is called a cograph. Such graphs are precisely the graphs that do not have the 4-vertex path as an induced subgraph. We define a $2$-cograph to be a graph in which the complement of every $2$-connected induced subgraph is not $2$-connected.
James Oxley, Jagdeep Singh
openalex +3 more sources
Confining the robber on cographs
Contributions to Discrete Mathematics, 2023 In a game of Cops and Robbers on graphs, usually the cops' objective is to capture the robber---a situation which the robber wants to avoid invariably. In this paper, we begin with introducing the notions of trapping and confining the robber and discussing their relations with capturing the robber.
Masood Masjoody
openalex +5 more sources
Sombor characteristic values of cographs. [PDF]
HeliyonA unique class of cograph is examined, that is defined recursively as C = C ( n 1 ) = K ‾ n 1 , and C = C ( n 1 , n 2 , … , n i ) = C ( n 1 , n 2 , … , n i - 1 ) ∪ K n i ‾ , for 2 ≤ i ≤ k . The Sombor spectrum of C is calculated, the Sombor spectral radius and establish the sharp bounds for the Sombor index, and the greatest and ...
Raza Z, Rather BA, Imran M.
europepmc +4 more sources
Minimal obstructions to $2$-polar cographs [PDF]
Discrete Applied Mathematics, 2017 Comment: 17 pages, 5 ...
Pavol Hell +2 more
openalex +5 more sources
Cographs: Eigenvalues and Dilworth number [PDF]
Discrete Mathematics, 2018 13 pages, Comments from referees ...
Ebrahim Ghorbani
openalex +5 more sources
Eigenvalue location in cographs [PDF]
Discrete Applied Mathematics, 2017 We give an $O(n)$ time and space algorithm for constructing a diagonal matrix congruent to A+xI, where A is the adjacency matrix of a cograph and $x\in \mathbb{R}$. Applications include determining the number of eigenvalues of a cograph's adjacency matrix that lie in any interval, obtaining a formula for the inertia of a cograph, and exhibiting ...
David P. Jacobs +2 more
openalex +5 more sources
On Some Combinatorial Problems in Cographs [PDF]
International Journal of Advances in Engineering Sciences and Applied Mathematics, 2018 21 pages, 4 ...
Kona Harshita, N. Sadagopan
openalex +4 more sources