Results 11 to 20 of about 438 (125)
Integral cographs and applications [PDF]
, 2019 A graph is called integral if all the eigenvalues of its adjacency matrix are integers. In this paper, we show a cograph that has a balanced cotree $T_{G}(a_{1},\ldots,a_{r-1},0|0,\ldots,0,a_{r})$ is integral computing its spectrum. As an application, these integral cographs can be used to estimate the eigenvalues of any cograph.
Luiz Emílio Allem, Fernando Tura
openalex +3 more sources
Orthology and near-cographs in the context of phylogenetic networks. [PDF]
Algorithms Mol BiolLindeberg A +3 more
europepmc +3 more sources
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
Mathematical Problems in Engineering, Volume 2022, Issue 1, 2022., 2022 In social network, users can manage their social network and social identity, publish information on various topics, and obtain information published by other users through friend relationship. The resulting large amount of text data attract more and more scholars to study it.
A. Yana, Ning Cao
wiley +1 more source
Graphon convergence of random cographs
Random Structures &Algorithms, Volume 59, Issue 3, Page 464-491, October 2021., 2021 Abstract We study the behavior of random labeled and unlabeled cographs with n vertices as n tends to infinity. We show that both models admit a novel random graphon W1/2 as distributional limit. Our main tool is an enhanced skeleton decomposition of the random Pólya tree with n leaves and no internal vertices having only one child.
Benedikt Stufler
wiley +1 more source
Intersection Cographs and Aesthetics
Journal of Humanistic Mathematics, 2022 Summary: Cographs are complete graphs with colored lines (edges); in an intersection cograph, the points (vertices) and lines (edges) are labeled by sets, and the line between each pair of points is (or represents) their intersection. This article first presents the elementary theory of intersection cographs: 15 are possible on 4 points; constraints on
openaire +2 more sources
Graphs and Combinatorics, 2023 A graph that can be generated from $K_1$ using joins and 0-sums is called a cograph. We define a sesquicograph to be a graph that can be generated from $K_1$ using joins, 0-sums, and 1-sums. We show that, like cographs, sesquicographs are closed under induced minors.
openaire +3 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 +4 more
wiley +1 more source