Results 31 to 40 of about 4,621 (198)
Longest and shortest cycles in random planar graphs
Random Structures &Algorithms, Volume 60, Issue 3, Page 462-505, May 2022., 2022 Abstract Let be a graph chosen uniformly at random from the class of all planar graphs on vertex set with edges. We study the cycle and block structure of when . More precisely, we determine the asymptotic order of the length of the longest and shortest cycle in in the critical range when .
Mihyun Kang, Michael Missethan
wiley +1 more source
Outerplanar and Planar Oriented Cliques [PDF]
Journal of Graph Theory, 2015 AbstractThe clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well‐known lower bound for the chromatic number of G. Every proper k‐coloring of G may be viewed as a homomorphism (an edge‐preserving vertex mapping) of G to the complete graph of order k.
Nandy, Ayan, Sen, Sagnik, Sopena, Éric
openaire +2 more sources
Site percolation and isoperimetric inequalities for plane graphs
Random Structures &Algorithms, Volume 58, Issue 1, Page 150-163, January 2021., 2021 We use isoperimetric inequalities combined with a new technique to prove upper bounds for the site percolation threshold of plane graphs with given minimum degree conditions. In the process we prove tight new isoperimetric bounds for certain classes of hyperbolic graphs.
John Haslegrave, Christoforos Panagiotis
wiley +1 more source
Nilpotent graphs with crosscap at most two
AKCE International Journal of Graphs and Combinatorics, 2018 Let be a commutative ring with identity. The nilpotent graph of , denoted by , is a graph with vertex set , and two vertices and are adjacent if and only if is nilpotent, where .
A. Mallika, R. Kala
doaj +2 more sources
Double domination in maximal outerplanar graphs
Open Mathematics, 2022 In graph GG, a vertex dominates itself and its neighbors. A subset S⊆V(G)S\subseteq V\left(G) is said to be a double-dominating set of GG if SS dominates every vertex of GG at least twice.
Zhuang Wei, Zheng Qiuju
doaj +1 more source
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs [PDF]
, 2016 We present space-efficient algorithms for computing cut vertices in a given graph with $n$ vertices and $m$ edges in linear time using $O(n+\min\{m,n\log \log n\})$ bits.
Kammer, Frank +2 more
core +2 more sources
Definability Equals Recognizability for $k$-Outerplanar Graphs [PDF]
, 2015 One of the most famous algorithmic meta-theorems states that every graph property that can be defined by a sentence in counting monadic second order logic (CMSOL) can be checked in linear time for graphs of bounded treewidth, which is known as Courcelle ...
Bodlaender, Hans L., Jaffke, Lars
core +5 more sources
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs [PDF]
, 2008 We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolation lemma as described in (Mulmuley et al.
Datta, Samir +2 more
core +7 more sources
The Degree-Diameter Problem for Outerplanar Graphs
Discussiones Mathematicae Graph Theory, 2017 For positive integers Δ and D we define nΔ,D to be the largest number of vertices in an outerplanar graph of given maximum degree Δ and diameter D. We prove that nΔ,D=ΔD2+O (ΔD2−1)$n_{\Delta ,D} = \Delta ^{{D \over 2}} + O\left( {\Delta ^{{D \over 2 ...
Dankelmann Peter +2 more
doaj +1 more source