Results 31 to 40 of about 567 (69)
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
Rainbow Disconnection in Graphs
Discussiones Mathematicae Graph Theory, 2018 Let G be a nontrivial connected, edge-colored graph. An edge-cut R of G is called a rainbow cut if no two edges in R are colored the same. An edge-coloring of G is a rainbow disconnection coloring if for every two distinct vertices u and v of G, there ...
Chartrand Gary +4 more
doaj +1 more source
On (strong) proper vertex-connection of graphs
, 2015 A path in a vertex-colored graph is a {\it vertex-proper path} if any two internal adjacent vertices differ in color. A vertex-colored graph is {\it proper vertex $k$-connected} if any two vertices of the graph are connected by $k$ disjoint vertex-proper
Jiang, Hui +3 more
core +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
On the Optimality of 3-Restricted Arc Connectivity for Digraphs and Bipartite Digraphs
Discussiones Mathematicae Graph Theory, 2022 Let D be a strong digraph. An arc subset S is a k-restricted arc cut of D if D − S has a strong component D′ with order at least k such that D\V (D′) contains a connected subdigraph with order at least k.
Zhang Yaoyao, Meng Jixiang
doaj +1 more source
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 +3 more
core
On Two Generalized Connectivities of Graphs
Discussiones Mathematicae Graph Theory, 2018 The concept of generalized k-connectivity κk(G), mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity.
Sun Yuefang, Li Fengwei, Jin Zemin
doaj +1 more source
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 +3 more
doaj +1 more source
Highly connected orientations from edge-disjoint rigid subgraphs
Forum of Mathematics, PiWe 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 +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 +1 more
doaj +1 more source