Results 21 to 30 of about 1,056 (209)
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
On the spread of outerplanar graphs
Special Matrices, 2022 The spread of a graph is the difference between the largest and most negative eigenvalue of its adjacency matrix. We show that for sufficiently large nn, the nn-vertex outerplanar graph with maximum spread is a vertex joined to a linear forest with Ω(n ...
Gotshall Daniel +2 more
doaj +1 more source
Free Choosability of Outerplanar Graphs [PDF]
Graphs and Combinatorics, 2015 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Aubry, Yves +2 more
openaire +2 more sources
Maximally Expressive GNNs for Outerplanar Graphs [PDF]
, 2023 We propose a linear time graph transformation that enables the Weisfeiler-Leman (WL) test and message passing graph neural networks (MPNNs) to be maximally expressive on outerplanar graphs.
Gärtner, Thomas; orcid: +8 more
core +3 more sources
A generalization of outerplanar graphs
Discrete Mathematics, 1984 A graph G is said to be W-outerplanar if it can be embedded in the plane so that all vertices of a given set \(W\subset V(G)\) lie on the boundary of one face. A characterization of such graphs is given by means of forbidden subgraphs, and an algorithm for W-outerplanarity testing is described. The results overlap, in part, with those of \textit{V.
Lía Oubiña, R. Zucchello
openaire +2 more sources
Generalized outerplanar index of a graph [PDF]
, 2018 summary:We define the generalized outerplanar index of a graph and give a full characterization of graphs with respect to this ...
Barati, Zahra
core +1 more source
A generalization of outerplanar graphs [PDF]
Časopis pro pěstování matematiky, 1988 A planar graph is said to be a generalized outerplanar graph if it has an embedding in the plane in which every edge is incident to a vertex laying on the boundary of the outer face. The author presents a characterization of generalized outerplanar graphs by means of a set of exactly 12 forbidden subgraphs (up to homeomorphism).
openaire +1 more source
On k-edge-magic labelings of maximal outerplanar graphs
AKCE International Journal of Graphs and Combinatorics, 2015 Let G be a graph with vertex set V and edge set E such that |V|=p and |E|=q. We denote this graph by (p,q)-graph. For integers k≥0, define a one-to-one map f from E to {k,k+1,…,k+q−1} and define the vertex sum for a vertex v as the sum of the labels of ...
Gee-Choon Lau +3 more
doaj +1 more source
Strong Chromatic Index of Outerplanar Graphs
Axioms, 2022 The strong chromatic index χs′(G) of a graph G is the minimum number of colors needed in a proper edge-coloring so that every color class induces a matching in G. It was proved In 2013, that every outerplanar graph G with Δ≥3 has χs′(G)≤3Δ−3.
Ying Wang +3 more
doaj +1 more source
Minimum Cycle Base of Graphs Identified by Two Planar Graphs [PDF]
, 2007 In this paper, we study the minimum cycle base of the planar graphs obtained from two 2-connected planar graphs by identifying an edge (or a cycle) of one graph with the corresponding edge (or cycle) of another, related with map geometries, i.e ...
Han, Ren, Dengju, Ma
core +1 more source