Results 11 to 20 of about 193 (188)
Modularity of minor‐free graphs
Journal of Graph Theory, 2022 AbstractWe prove that a class of graphs with excluded minor and with the maximum degree of smaller order than the number of edges is maximally modular, that is, for every , the modularity of any graph in the class with sufficiently many edges is at least .
Michal Lason, Malgorzata Sulkowska
openaire +2 more sources
Shift operators from the simplex representation in momentum-space CFT
Journal of High Energy Physics, 2023 We derive parametric integral representations for the general n-point function of scalar operators in momentum-space conformal field theory. Recently, this was shown to be expressible as a generalised Feynman integral with the topology of an (n − 1 ...
Francesca Caloro, Paul McFadden
doaj +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
Structure of Projective Planar Subgraphs of the Graph Obstructions for Fixed Surface
Кібернетика та комп'ютерні технології, 2022 Consider the problem of studying the metric properties of a subgraph G \ v, where v is an arbitrary vertex of obstruction graphs G of a nonorientable genus, which will determine the sets of points of attachment of one subgraph to another and allow ...
Volodymyr Petrenjuk +2 more
doaj +1 more source
The Minor Crossing Number of Graphs with an Excluded Minor [PDF]
The Electronic Journal of Combinatorics, 2008 The minor crossing number of a graph $G$ is the minimum crossing number of a graph that contains $G$ as a minor. It is proved that for every graph $H$ there is a constant $c$, such that every graph $G$ with no $H$-minor has minor crossing number at most $c|V(G)|$.
Bokal, Drago +2 more
openaire +5 more sources
Asymptotic properties of some minor-closed classes of graphs (conference version) [PDF]
Discrete Mathematics & Theoretical Computer Science, 2013 Let $\mathcal{A}$ be a minor-closed class of labelled graphs, and let $G_n$ be a random graph sampled uniformly from the set of n-vertex graphs of $\mathcal{A}$. When $n$ is large, what is the probability that $G_n$ is connected? How many components does
Mireille Bousquet-Mélou, Kerstin Weller
doaj +1 more source
Two lower bounds for $p$-centered colorings [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 Given a graph $G$ and an integer $p$, a coloring $f : V(G) \to \mathbb{N}$ is \emph{$p$-centered} if for every connected subgraph $H$ of $G$, either $f$ uses more than $p$ colors on $H$ or there is a color that appears exactly once in $H$. The notion of $
Loïc Dubois +4 more
doaj +1 more source
Consensus analysis of the weighted corona networks
Frontiers in Physics, 2022 The consensus of complex networks has attracted the attention of many scholars. The graph operation is a common method to construct complex networks, which is helpful in studying the consensus of complex networks. Based on the corona networks G1◦G2, this
Weiwei Du +3 more
doaj +1 more source
Reconfiguration of graph minors
CoRR, 2018 Under the reconfiguration framework, we consider the various ways that a target graph $H$ is a {\em minor} of a host graph $G$, where a subgraph of $G$ can be transformed into $H$ by means of {\em edge contraction} (replacement of both endpoints of an edge by a new vertex adjacent to any vertex adjacent to either endpoint).
Benjamin R. Moore +2 more
openaire +4 more sources
Complete graph minors and the graph minor structure theorem
Journal of Combinatorial Theory, Series B, 2013 The graph minor structure theorem by Robertson and Seymour shows that every graph that excludes a fixed minor can be constructed by a combination of four ingredients: graphs embedded in a surface of bounded genus, a bounded number of vortices of bounded width, a bounded number of apex vertices, and the clique-sum operation.
Gwenaël Joret, David R. Wood
openaire +3 more sources