Results 41 to 50 of about 590 (74)

Note on minimally $k$-rainbow connected graphs [PDF]

, 2012
An edge-colored graph $G$, where adjacent edges may have the same color, is {\it rainbow connected} if every two vertices of $G$ are connected by a path whose edge has distinct colors.
Li, Hengzhe, Li, Xueliang, Sun, Yuefang, Zhao, Yan   +3 more
core  

Generalized Rainbow Connection of Graphs and their Complements

Discussiones Mathematicae Graph Theory, 2018
Let G be an edge-colored connected graph. A path P in G is called ℓ-rainbow if each subpath of length at most ℓ + 1 is rainbow. The graph G is called (k, ℓ)-rainbow connected if there is an edge-coloring such that every pair of distinct vertices of G is ...
Li Xueliang, Magnant Colton, Wei Meiqin, Zhu Xiaoyu   +3 more
doaj   +1 more source

On the super connectivity of Kronecker products of graphs [PDF]

, 2011
In this paper we present the super connectivity of Kronecker product of a general graph and a complete graph.Comment: 8 ...
Shan, Erfang, Wang, Hechao
core  

Highly connected orientations from edge-disjoint rigid subgraphs

Forum of Mathematics, Pi
We give an affirmative answer to a long-standing conjecture of Thomassen, stating that every sufficiently highly connected graph has a k-vertex-connected orientation. We prove that a connectivity of order $O(k^2)$ suffices.
Dániel Garamvölgyi, Tibor Jordán, Csaba Király, Soma Villányi   +3 more
doaj   +1 more source

The Super-Connectivity of Kneser Graphs

Discussiones Mathematicae Graph Theory, 2019
A vertex cut of a connected graph G is a set of vertices whose deletion disconnects G. A connected graph G is super-connected if the deletion of every minimum vertex cut of G isolates a vertex.
Ekinci Gülnaz Boruzanli, Gauci John Baptist   +1 more
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

Edge-Fault Tolerance of Hypercube-like Networks [PDF]

, 2012
This paper considers a kind of generalized measure $\lambda_s^{(h)}$ of fault tolerance in a hypercube-like graph $G_n$ which contain several well-known interconnection networks such as hypercubes, varietal hypercubes, twisted cubes, crossed cubes and M\"
Li, Xiang-Jun, Xu, Jun-Ming
core  

Under which conditions is λ″(G)=κ″(L(G))?

AKCE International Journal of Graphs and Combinatorics, 2023
In this paper we show that if G is a connected graph such that [Formula: see text], [Formula: see text] and [Formula: see text] then [Formula: see text] exists and [Formula: see text] if and only if G is not super-[Formula: see text]. We also obtain some
Farnaz Soliemany, Mohsen Ghasemi, Rezvan Varmazyar   +2 more
doaj   +1 more source

Rainbow connection in $3$-connected graphs [PDF]

, 2010
An edge-colored graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in ...
Li, Xueliang, Shi, Yongtang
core  

Characterizing Atoms that Result from Decomposition by Clique Separators

Discussiones Mathematicae Graph Theory, 2017
A graph is defined to be an atom if no minimal vertex separator induces a complete subgraph; thus, atoms are the graphs that are immune to clique separator decomposition.
McKee Terry A.
doaj   +1 more source