Results 21 to 30 of about 64 (62)
On the Connectivity of Token Graphs of Trees [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Let $k$ and $n$ be integers such that $1\leq k \leq n-1$, and let $G$ be a simple graph of order $n$. The $k$-token graph $F_k(G)$ of $G$ is the graph whose vertices are the $k$-subsets of $V(G)$, where two vertices are adjacent in $F_k(G)$ whenever ...
Ruy Fabila-Monroy +2 more
doaj +1 more source
Rainbow Connection Number of Graphs with Diameter 3
Discussiones Mathematicae Graph Theory, 2017 A path in an edge-colored graph G is rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest integer k for which there exists a k-edge-coloring of G such that every pair of distinct vertices of G
Li Hengzhe, Li Xueliang, Sun Yuefang
doaj +1 more source
Distance-Local Rainbow Connection Number
Discussiones Mathematicae Graph Theory, 2022 Under an edge coloring (not necessarily proper), a rainbow path is a path whose edge colors are all distinct. The d-local rainbow connection number lrcd(G) (respectively, d-local strong rainbow connection number lsrcd(G)) is the smallest number of colors
Septyanto Fendy, Sugeng Kiki A.
doaj +1 more source
Asymptotically sharpening the $s$-Hamiltonian index bound [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 For a non-negative integer $s\le |V(G)|-3$, a graph $G$ is $s$-Hamiltonian if the removal of any $k\le s$ vertices results in a Hamiltonian graph. Given a connected simple graph $G$ that is not isomorphic to a path, a cycle, or a $K_{1,3}$, let $\delta(G)
Sulin Song +3 more
doaj +1 more source
On the Maximum and Minimum Sizes of a Graph with Given k-Connectivity
Discussiones Mathematicae Graph Theory, 2017 The concept of k-connectivity κk(G), introduced by Chartrand in 1984, is a generalization of the cut-version of the classical connectivity. For an integer k ≥ 2, the k-connectivity of a connected graph G with order n ≥ k is the smallest number of ...
Sun Yuefang
doaj +1 more source
More Aspects of Arbitrarily Partitionable Graphs
Discussiones Mathematicae Graph Theory, 2022 A graph G of order n is arbitrarily partitionable (AP) if, for every sequence (n1, . . ., np) partitioning n, there is a partition (V1, . . ., ,Vp) of V (G) such that G[Vi] is a connected ni-graph for i = 1, . . ., p.
Bensmail Julien, Li Binlong
doaj +1 more source
Minimally Strong Subgraph (k,ℓ)-Arc-Connected Digraphs
Discussiones Mathematicae Graph Theory, 2022 Let D = (V,A) be a digraph of order n, S a subset of V of size k and 2 ≤ k ≤ n. A subdigraph H of D is called an S-strong subgraph if H is strong and S ⊆ V (H). Two S-strong subgraphs D1 and D2 are said to be arc-disjoint if A(D1) ∩ A(D2) = ∅.
Sun Yuefang, Jin Zemin
doaj +1 more source
Removable Edges on a Hamilton Cycle or Outside a Cycle in a 4-Connected Graph
Discussiones Mathematicae Graph Theory, 2021 Let G be a 4-connected graph. We call an edge e of G removable if the following sequence of operations results in a 4-connected graph: delete e from G; if there are vertices with degree 3 in G− e, then for each (of the at most two) such vertex x, delete ...
Wu Jichang +3 more
doaj +1 more source
Deficiency and Forbidden Subgraphs of Connected, Locally-Connected Graphs
Discussiones Mathematicae Graph Theory, 2020 A graph G is locally-connected if the neighbourhood NG(v) induces a connected subgraph for each vertex v in G. For a graph G, the deficiency of G is the number of vertices unsaturated by a maximum matching, denoted by def(G). In fact, the deficiency of a
Li Xihe, Wang Ligong
doaj +1 more source
The super-connectivity of Johnson graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 For positive integers $n,k$ and $t$, the uniform subset graph $G(n, k, t)$ has all $k$-subsets of $\{1,2,\ldots, n\}$ as vertices and two $k$-subsets are joined by an edge if they intersect at exactly $t$ elements.
Gülnaz Boruzanlı Ekinci +1 more
doaj +1 more source