Results 61 to 70 of about 3,724 (174)
A Polynomial-time Algorithm for Outerplanar Diameter Improvement
, 2014 The Outerplanar Diameter Improvement problem asks, given a graph $G$ and an integer $D$, whether it is possible to add edges to $G$ in a way that the resulting graph is outerplanar and has diameter at most $D$.
Cohen, Nathann +6 more
core +3 more sources
Recognizing Trees From Incomplete Decks
Journal of Graph Theory, Volume 110, Issue 3, Page 322-336, November 2025.ABSTRACT Given a graph G, the unlabeled subgraphs G − v are called the cards of G. The deck of G is the multiset { G − v : v ∈ V ( G ) }. Wendy Myrvold showed that a disconnected graph and a connected graph both on n vertices have at most ⌊ n 2 ⌋ + 1 cards in common and found (infinite) families of trees and disconnected forests for which this upper ...
Gabriëlle Zwaneveld
wiley +1 more source
Vertex-Coloring with Star-Defects
, 2016 Defective coloring is a variant of traditional vertex-coloring, according to which adjacent vertices are allowed to have the same color, as long as the monochromatic components induced by the corresponding edges have a certain structure.
A Edelman +19 more
core +1 more source
On Endomorphism Universality of Sparse Graph Classes
Journal of Graph Theory, Volume 110, Issue 2, Page 223-244, October 2025.ABSTRACT We show that every commutative idempotent monoid (a.k.a. lattice) is the endomorphism monoid of a subcubic graph. This solves a problem of Babai and Pultr and the degree bound is best‐possible. On the other hand, we show that no class excluding a minor can have all commutative idempotent monoids among its endomorphism monoids. As a by‐product,
Kolja Knauer, Gil Puig i Surroca
wiley +1 more source
(2,1)-Total labelling of outerplanar graphs
Discrete Applied Mathematics, 2007 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Chen, Dong, Wang, Weifan
openaire +1 more source
Algorithm-based radio labeling for optimal channel assignment in outerplanar graphs
Frontiers in Computer ScienceIntroductionRadio labeling of graphs extends the channel assignment problem by assigning non-negative integers to vertices of a connected graph G such that |h(℘)−h(𝓆)|≥diam(ℊ)+1−d(℘, 𝓆).
Baskar Mari, Ravi Sankar Jeyaraj
doaj +1 more source
Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 We study the uniform random graph $\mathsf{C}_n$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph $\mathsf{C}_n / \sqrt{n}$ converges to the Brownian Continuum Random Tree $\mathcal{T}_ ...
Konstantinos Panagiotou +2 more
doaj +1 more source
Pixel and Voxel Representations of Graphs
, 2015 We study contact representations for graphs, which we call pixel representations in 2D and voxel representations in 3D. Our representations are based on the unit square grid whose cells we call pixels in 2D and voxels in 3D.
A Bezdek +31 more
core +1 more source
Tight Distance Query Reconstruction for Trees and Graphs Without Long Induced Cycles
Random Structures &Algorithms, Volume 66, Issue 4, July 2025.ABSTRACT Given access to the vertex set V$$ V $$ of a connected graph G=(V,E)$$ G=\left(V,E\right) $$ and an oracle that given two vertices u,v∈V$$ u,v\in V $$, returns the shortest path distance between u$$ u $$ and v$$ v $$, how many queries are needed to reconstruct E$$ E $$?
Paul Bastide, Carla Groenland
wiley +1 more source
L(h,1,1)-Labeling of Outerplanar Graphs [PDF]
Mathematical Methods of Operations Research, 2006 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
CALAMONERI, Tiziana +3 more
openaire +11 more sources