Results 11 to 20 of about 1,010 (104)
Longer Cycles in Essentially 4-Connected Planar Graphs
Discussiones Mathematicae Graph Theory, 2020 A planar 3-connected graph G is called essentially 4-connected if, for every 3-separator S, at least one of the two components of G − S is an isolated vertex.
Fabrici Igor +3 more
doaj +1 more source
An O(mn2) Algorithm for Computing the Strong Geodetic Number in Outerplanar Graphs
Discussiones Mathematicae Graph Theory, 2022 Let G = (V (G), E(G)) be a graph and S be a subset of vertices of G. Let us denote by γ[u, v] a geodesic between u and v. Let Γ(S) = {γ[vi, vj] | vi, vj ∈ S} be a set of exactly |S|(|S|−1)/2 geodesics, one for each pair of distinct vertices in S.
Mezzini Mauro
doaj +1 more source
A simple and elementary proof of Whitney's unique embedding theorem
, 2020 In this note we give a short and elementary proof of a more general version of Whitney's theorem that 3-connected planar graphs have a unique embedding in the plane.
Brinkmann, Gunnar
core +1 more source
Long-Scale Ollivier Ricci Curvature of Graphs
Analysis and Geometry in Metric Spaces, 2019 We study the long-scale Ollivier Ricci curvature of graphs as a function of the chosen idleness. Similarly to the previous work on the short-scale case, we show that this idleness function is concave and piecewise linear with at most 3 linear parts.
Cushing D., Kamtue S.
doaj +1 more source
Discussiones Mathematicae Graph Theory, 2023 DP-coloring is generalized via relaxed coloring and variable degeneracy in [P. Sittitrai and K. Nakprasit, Su cient conditions on planar graphs to have a relaxed DP-3-coloring, Graphs Combin. 35 (2019) 837–845], [K.M. Nakprasit and K.
Sribunhung Sarawute +3 more
doaj +1 more source
A Note on the Maximum Genus of Graphs with Diameter 4 [PDF]
, 2007 Let G be a simple graph with diameter four, if G does not contain complete subgraph K3 of order ...
Lin, Zhao, WeiLi, He, Xiang, Ren
core +1 more source
Improved Bounds for Some Facially Constrained Colorings
Discussiones Mathematicae Graph Theory, 2023 A facial-parity edge-coloring of a 2-edge-connected plane graph is a facially-proper edge-coloring in which every face is incident with zero or an odd number of edges of each color. A facial-parity vertex-coloring of a 2-connected plane graph is a proper
Štorgel Kenny
doaj +1 more source
A note on the Cops & Robber game on graphs embedded in non-orientable surfaces [PDF]
, 2011 The Cops and Robber game is played on undirected finite graphs. A number of cops and one robber are positioned on vertices and take turns in sliding along edges. The cops win if they can catch the robber.
A. Berarducci +10 more
core +2 more sources
Additive List Coloring of Planar Graphs with Given Girth
Discussiones Mathematicae Graph Theory, 2020 An additive coloring of a graph G is a labeling of the vertices of G from {1, 2, . . . , k} such that two adjacent vertices have distinct sums of labels on their neighbors.
Brandt Axel +2 more
doaj +1 more source
Finite planar emulators for K_{4,5} - 4K_2 and K_{1,2,2,2} and Fellows' Conjecture [PDF]
, 2009 In 1988 Fellows conjectured that if a finite, connected graph admits a finite planar emulator, then it admits a finite planar cover. We construct a finite planar emulator for K_{4,5} - 4K_2.
Archdeacon +10 more
core +2 more sources