Results 11 to 20 of about 1,423 (126)
Graphon convergence of random cographs [PDF]
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 +2 more sources
A linear algorithm for obtaining the Laplacian eigenvalues of a cograph
Special MatricesIn this article, we give an O(n)O\left(n) time and space algorithm for obtaining the Laplacian eigenvalues of a cograph. This approach is more efficient as there is no need to directly compute the eigenvalues of Laplacian matrix related to this class of ...
Chen Guantao, Tura Fernando C.
doaj +2 more sources
Infinite cographs and chain complete N-free posets [PDF]
, 2018 We give a necessary and sufficient condition for a $P_4$-free graph to be a cograph. This allows us to obtain a simple proof of the fact that finite $P_4$-free graphs are finite cographs. We also prove that chain complete posets whose comparability graph
Zaguia, Imed
core +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
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
Removing Twins in Graphs to Break Symmetries
Mathematics, 2019 Determining vertex subsets are known tools to provide information about automorphism groups of graphs and, consequently about symmetries of graphs. In this paper, we provide both lower and upper bounds of the minimum size of such vertex subsets, called ...
Antonio González, María Luz Puertas
doaj +1 more source
A note on the convexity number for complementary prisms [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 In the geodetic convexity, a set of vertices $S$ of a graph $G$ is $\textit{convex}$ if all vertices belonging to any shortest path between two vertices of $S$ lie in $S$. The cardinality $con(G)$ of a maximum proper convex set $S$ of $G$ is the $\textit{
Diane Castonguay +3 more
doaj +1 more source
Signed graphs with integral net Laplacian spectrum
AKCE International Journal of Graphs and Combinatorics, 2023 Given a signed graph [Formula: see text], let [Formula: see text] and [Formula: see text] be its standard adjacency matrix and the diagonal matrix of net-degrees, respectively.
M. Anđelić +3 more
doaj +1 more source