Results 11 to 20 of about 1,967 (126)
Theory and Applications of GraphsA class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by G^{apex} the class of graphs G that contain a vertex v such that G − v is in G.
Jagdeep Singh +2 more
doaj +5 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
An efficient g-centroid location algorithm for cographs
International Journal of Mathematics and Mathematical Sciences, 2005 In 1998, Pandu Rangan et al. Proved that locating the g‐centroid for an arbitrary graph is 𝒩𝒫‐hard by reducing the problem of finding the maximum clique size of a graph to the g‐centroid location problem. They have also given an efficient polynomial time algorithm for locating the g‐centroid for maximal outerplanar graphs, Ptolemaic graphs, and split ...
V. Prakash
doaj +2 more sources
Characterization of protein complexes and subcomplexes in protein-protein interaction databases. [PDF]
Biochem Res Int, 2015 The identification and characterization of protein complexes implicated in protein‐protein interaction data are crucial to the understanding of the molecular events under normal and abnormal physiological conditions. This paper provides a novel characterization of subcomplexes in protein interaction databases, stressing definition and representation ...
Zaki N, Mohamed EA, Mora A.
europepmc +2 more sources
Generalizing Cographs to 2-Cographs
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.
Oxley, James, Singh, Jagdeep
openaire +2 more sources
Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Let $G=(V(G),E(G))$ be a finite simple undirected graph with vertex set $V(G)$, edge set $E(G)$ and vertex subset $S\subseteq V(G)$. $S$ is termed \emph{open-dominating} if every vertex of $G$ has at least one neighbor in $S$, and \emph{open-independent,
Márcia R. Cappelle +3 more
doaj +1 more source
On Rödl's Theorem for Cographs
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$.
Gishboliner, Lior, Shapira, Asaf
openaire +1 more source
Erdős–Hajnal for graphs with no 5‐hole
Proceedings of the London Mathematical Society, Volume 126, Issue 3, Page 997-1014, March 2023., 2023 Abstract The Erdős–Hajnal conjecture says that for every graph H$H$ there exists τ>0$\tau >0$ such that every graph G$G$ not containing H$H$ as an induced subgraph has a clique or stable set of cardinality at least |G|τ$|G|^\tau$. We prove that this is true when H$H$ is a cycle of length five.
Maria Chudnovsky +3 more
wiley +1 more source
On the path partition number of 6‐regular graphs
Journal of Graph Theory, Volume 101, Issue 3, Page 345-378, November 2022., 2022 Abstract A path partition (also referred to as a linear forest) of a graph G $G$ is a set of vertex‐disjoint paths which together contain all the vertices of G $G$. An isolated vertex is considered to be a path in this case. The path partition conjecture states that every n $n$‐vertex d $d$‐regular graph has a path partition with at most n d + 1 $\frac{
Uriel Feige, Ella Fuchs
wiley +1 more source
Enumerating conjugacy classes of graphical groups over finite fields
Bulletin of the London Mathematical Society, Volume 54, Issue 5, Page 1923-1943, October 2022., 2022 Abstract Each graph and choice of a commutative ring gives rise to an associated graphical group. In this article, we introduce and investigate graph polynomials that enumerate conjugacy classes of graphical groups over finite fields according to their sizes.
Tobias Rossmann
wiley +1 more source