Results 31 to 40 of about 119 (107)
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
Feedback Arc Number and Feedback Vertex Number of Cartesian Product of Directed Cycles
Discrete Dynamics in Nature and Society, Volume 2019, Issue 1, 2019., 2019 For a digraph D, the feedback vertex number τ(D), (resp. the feedback arc number τ′(D)) is the minimum number of vertices, (resp. arcs) whose removal leaves the resultant digraph free of directed cycles. In this note, we determine τ(D) and τ′(D) for the Cartesian product of directed cycles D=Cn1→□Cn2→□…Cnk→. Actually, it is shown that τ′D=n1n2…nk∑i=1k1/
Xiaohong Chen +2 more
wiley +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
Geometric Assortative Growth Model for Small‐World Networks
The Scientific World Journal, Volume 2014, Issue 1, 2014., 2014 It has been shown that both humanly constructed and natural networks are often characterized by small‐world phenomenon and assortative mixing. In this paper, we propose a geometrically growing model for small‐world networks. The model displays both tunable small‐world phenomenon and tunable assortativity.
Yilun Shang, H. M. Chamberlin, Y. Zhang
wiley +1 more source
Total domination in maximal outerplanar graphs
Discrete Applied Mathematics, 2017 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Dorfling, Michael +2 more
openaire +1 more source
On vertex‐transitive graphs with a unique hamiltonian cycle
Journal of Graph Theory, Volume 108, Issue 1, Page 65-99, January 2025.Abstract A graph is said to be uniquely hamiltonian if it has a unique hamiltonian cycle. For a natural extension of this concept to infinite graphs, we find all uniquely hamiltonian vertex‐transitive graphs with finitely many ends, and also discuss some examples with infinitely many ends.
Babak Miraftab, Dave Witte Morris
wiley +1 more source
Double domination in maximal outerplanar graphs
, 2021 In a graph $G$, a vertex dominates itself and its neighbors. A subset $S\subseteq V(G)$ is said to be a double dominating set of $G$ if $S$ dominates every vertex of $G$ at least twice. The double domination number $ _{\times 2}(G)$ is the minimum cardinality of a double dominating set of $G$.
openaire +2 more sources
Symmetry breaking in planar and maximal outerplanar graphs [PDF]
Discrete Mathematics, Algorithms and Applications, 2019 The distinguishing number (index) [Formula: see text] ([Formula: see text]) of a graph [Formula: see text] is the least integer [Formula: see text] such that [Formula: see text] has a vertex (edge) labeling with [Formula: see text] labels that is preserved only by a trivial automorphism.
Alikhani, Saeid, Soltani, Samaneh
openaire +3 more sources
On the Hub Number of Ring Graphs and Their Behavior Under Graph Operations
International Journal of Mathematics and Mathematical Sciences, Volume 2025, Issue 1, 2025.This study examines the hub number of ring graphs and investigates their behavior under operations such as union, intersection, and join. Different findings for this parameter are found for a variety of types of ring graphs, such as commutative ring graphs, path ring graphs, complete ring graphs, cycle ring graphs, and star ring graphs, for which the ...
Mohammed Alsharafi +3 more
wiley +1 more source
Self‐avoiding walks and polygons on hyperbolic graphs
Journal of Graph Theory, Volume 106, Issue 3, Page 435-473, July 2024.Abstract We prove that for the d $d$‐regular tessellations of the hyperbolic plane by k $k$‐gons, there are exponentially more self‐avoiding walks of length n $n$ than there are self‐avoiding polygons of length n $n$. We then prove that this property implies that the self‐avoiding walk is ballistic, even on an arbitrary vertex‐transitive graph ...
Christoforos Panagiotis
wiley +1 more source