Results 11 to 20 of about 412 (107)
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
openalex +2 more sources
P_4-Colorings and P_4-Bipartite Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 A vertex partition of a graph into disjoint subsets V_is is said to be a P_4-free coloring if each color class V_i induces a subgraph without chordless path on four vertices (denoted by P_4).
Chinh T. Hoàng, Van Bang Le
doaj +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
Capturing Polynomial Time using Modular Decomposition [PDF]
Logical Methods in Computer Science, 2019 The question of whether there is a logic that captures polynomial time is one of the main open problems in descriptive complexity theory and database theory.
Berit Grußien
doaj +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
Sum structures in abelian groups
Examples and Counterexamples, 2023 Any set S of elements from an abelian group produces a graph with colored edges G(S), with its points the elements of S, and the edge between points P and Q assigned for its “color” the sum P+Q.
Robert Haas
doaj +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