Results 71 to 80 of about 1,967 (126)
On the Edge‐Density of the Brownian Co‐Graphon and Common Ancestors of Pairs in the CRT
Random Structures &Algorithms, Volume 66, Issue 1, January 2025.ABSTRACT Bassino et al. have shown that uniform random co‐graphs (graphs without induced P4$$ {P}_4 $$) of size n$$ n $$ converge to a certain non‐deterministic graphon. The edge density of this graphon is a random variable Λ∈[0,1]$$ \boldsymbol{\Lambda} \in \left[0,1\right] $$ whose first moments have been computed by these authors.
Guillaume Chapuy
wiley +1 more source
, 2019 Cographs--defined most simply as complete graphs with colored lines--both dualize and generalize ordinary graphs, and promise a comparably wide range of applications. This article introduces them by examples, catalogues, and elementary properties. Any finite cograph may be realized in several ways, including inner products, polynomials, geometrically ...
openaire +2 more sources
The pathwidth and treewidth of cographs [PDF]
SIAM Journal on Discrete Mathematics, 1990 Summary: It is shown that the pathwidth of a cograph equals its treewidth, and a linear time algorithm to determine the pathwidth of a cograph and build a corresponding path-decomposition is given.
Bodlaender, Hans, Möhring, Rolf H.
openaire +2 more sources
Scheduling on uniform machines with a conflict graph: complexity and resolution
International Transactions in Operational Research, Volume 31, Issue 2, Page 863-888, March 2024.Abstract This paper deals with the problem of scheduling a set of unit‐time jobs on a set of uniform machines. The jobs are subject to conflict constraints modeled by a graph G called the conflict graph, in which adjacent jobs cannot be processed on a same machine.
Amin Mallek, Mourad Boudhar
wiley +1 more source
Feynman graph generation and calculations in the Hopf algebra of Feynman graphs
, 2014 Two programs for the computation of perturbative expansions of quantum field theory amplitudes are provided. feyngen can be used to generate Feynman graphs for Yang-Mills, QED and $\varphi^k$ theories.
Borinsky, Michael
core +1 more source
On some combinatorial problems in cographs [PDF]
International Journal of Advances in Engineering Sciences and Applied Mathematics, 2019 21 pages, 4 ...
Harshita Kona, N. Sadagopan
openaire +2 more sources
Defining and identifying cograph communities in complex networks
New Journal of Physics, 2015 Community or module detection is a fundamental problem in complex networks. Most of the traditional algorithms available focus only on vertices in a subgraph that are densely connected among themselves while being loosely connected to the vertices ...
Songwei Jia +6 more
doaj +1 more source
On some Graphs with a Unique Perfect Matching
, 2017 We show that deciding whether a given graph $G$ of size $m$ has a unique perfect matching as well as finding that matching, if it exists, can be done in time $O(m)$ if $G$ is either a cograph, or a split graph, or an interval graph, or claw-free ...
Chaplick, S. +3 more
core +1 more source
Integral cographs and applications
, 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.
Allem, Luiz Emilio, Tura, Fernando
openaire +2 more sources
Graphic splitting of cographic matroids
Discussiones Mathematicae Graph Theory, 2015 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +3 more sources