Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "connectivity" wg kryterium: Wszystkie pola

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 42
Tytuł:
Bounding neighbor-connectivity of Abelian Cayley graphs
Autorzy:
Doty, Lynne
Powiązania:
https://bibliotekanauki.pl/articles/743950.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Cayley graphs
neighbor-connectivity bound
Opis:
For the notion of neighbor-connectivity in graphs whenever a vertex is subverted the entire closed neighborhood of the vertex is deleted from the graph. The minimum number of vertices whose subversion results in an empty, complete, or disconnected subgraph is called the neighbor-connectivity of the graph. Gunther, Hartnell, and Nowakowski have shown that for any graph, neighbor-connectivity is bounded above by κ. Doty has sharpened that bound in abelian Cayley graphs to approximately (1/2)κ. The main result of this paper is the constructive development of an alternative, and often tighter, bound for abelian Cayley graphs through the use of an auxiliary graph determined by the generating set of the abelian Cayley graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 3; 475-491
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Connectivity of path graphs
Autorzy:
Knor, Martin
Niepel, L'udovít
Powiązania:
https://bibliotekanauki.pl/articles/743766.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
connectivity
path graph
cycle
Opis:
We prove a necessary and sufficient condition under which a connected graph has a connected P₃-path graph. Moreover, an analogous condition for connectivity of the Pₖ-path graph of a connected graph which does not contain a cycle of length smaller than k+1 is derived.
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 2; 181-195
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Minimum Size of a Graph with Given Tree Connectivity
Autorzy:
Sun, Yuefang
Sheng, Bin
Jin, Zemin
Powiązania:
https://bibliotekanauki.pl/articles/32083875.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
generalized connectivity
tree connectivity
eneralized k-connectivity
generalized k-edge-connectivity
packing
Opis:
For a graph $G = (V, E)$ and a set $S ⊆ V$ of at least two vertices, an $S$-tree is a such subgraph $T$ of $G$ that is a tree with $S ⊆ V(T)$. Two $S$-trees $T_1$ and $T_2$ are said to be internally disjoint if $E(T_1) ∩ E(T_2) = ∅$ and $V(T_1) ∩ V(T_2) = S$, and edge-disjoint if $E(T_1) ∩ E(T_2) = ∅$. The generalized local connectivity $κ_G(S)$ (generalized local edge-connectivity $λ_G(S)$, respectively) is the maximum number of internally disjoint (edge-disjoint, respectively) $S$-trees in $G$. For an integer $k$ with $2 ≤ k ≤ n$, the generalized $k$-connectivity (generalized $k$-edge-connectivity, respectively) is defined as $κ_k(G) = min{κ_G(S) | S ⊆ V(G), |S| = k} (λ_k(G) = min{λ_G(S) | S ⊆ V(G), |S| = k}$, respectively). Let $f(n, k, t)$ ($g(n, k, t)$, respectively) be the minimum size of a connected graph $G$ with order $n$ and $κ_k(G) = t$ ($λ_k(G) = t$, respectively), where $3 ≤ k ≤ n$ and \(1≤t≤n-⌈\frac{k}{2}⌉\). For general $k$ and $t$, Li and Mao obtained a lower bound for $g(n, k, t)$ which is tight for the case $k = 3$. We show that the bound also holds for $f(n, k, t)$ and is tight for the case $k = 3$. When t is general, we obtain upper bounds of both $f(n, k, t)$ and $g(n, k, t)$ for $k ∈ {3, 4, 5}$, and all of these bounds can be attained. When $k$ is general, we get an upper bound of $g(n, k, t)$ for $t ∈ {1, 2, 3, 4}$ and an upper bound of $f(n, k, t)$ for $t ∈ {1, 2, 3}$. Moreover, both bounds can be attained.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 409-425
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Maximum and Minimum Sizes of a Graph with Given k-Connectivity
Autorzy:
Sun, Yuefang
Powiązania:
https://bibliotekanauki.pl/articles/31341709.pdf
Data publikacji:
2017-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
k -connectivity
generalized connectivity
connectivity
Opis:
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 vertices whose removal from G produces a graph with at least k components or a graph with fewer than k vertices. In this paper, we get a sharp upper bound for the size of G with κk(G) = t, where 1 ≤ t ≤ n − k and k ≥ 3; moreover, the unique extremal graph is given. Based on this result, we get the exact values for the maximum size, denoted by g(n, k, t), of a connected graph G with order n and κk(G) = t. We also compute the exact values and bounds for another parameter f(n, k, t) which is defined as the minimum size of a connected graph G with order n and κk(G) = t, where 1 ≤ t ≤ n − k and k ≥ 3.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 3; 623-632
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Edge-connectivity of strong products of graphs
Autorzy:
Bresar, Bostjan
Spacapan, Simon
Powiązania:
https://bibliotekanauki.pl/articles/743791.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
connectivity
strong product
graph product
separating set
Opis:
The strong product G₁ ⊠ G₂ of graphs G₁ and G₂ is the graph with V(G₁)×V(G₂) as the vertex set, and two distinct vertices (x₁,x₂) and (y₁,y₂) are adjacent whenever for each i ∈ {1,2} either $x_i = y_i$ or $x_i y_i ∈ E(G_i)$. In this note we show that for two connected graphs G₁ and G₂ the edge-connectivity λ (G₁ ⊠ G₂) equals min{δ(G₁ ⊠ G₂), λ(G₁)(|V(G₂)| + 2|E(G₂)|), λ(G₂)(|V(G₁)| + 2|E(G₁)|)}. In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 2; 333-343
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On distance local connectivity and vertex distance colouring
Autorzy:
Holub, Přemysl
Powiązania:
https://bibliotekanauki.pl/articles/743741.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
degree condition
distance local connectivity
distance chromatic number
Opis:
In this paper, we give some sufficient conditions for distance local connectivity of a graph, and a degree condition for local connectivity of a k-connected graph with large diameter. We study some relationships between t-distance chromatic number and distance local connectivity of a graph and give an upper bound on the t-distance chromatic number of a k-connected graph with diameter d.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 2; 209-227
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Super-Connectivity of Kneser Graphs
Autorzy:
Ekinci, Gülnaz Boruzanli
Gauci, John Baptist
Powiązania:
https://bibliotekanauki.pl/articles/31343789.pdf
Data publikacji:
2019-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
connectivity
super-connectivity
Kneser graphs
Opis:
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. The super-connectivity is the size of the smallest vertex cut of $G$ such that each resultant component does not have an isolated vertex. The Kneser graph $KG(n, k)$ is the graph whose vertices are the $k$-subsets of ${1, 2, . . ., n}$ and two vertices are adjacent if the $k$-subsets are disjoint. We use Baranyai’s Theorem on the decompositions of complete hypergraphs to show that the Kneser graph $KG$ are super-connected when $n \ge 5$ and that their super-connectivity is \( \binom{n}{2} − 6 \) when $ n \ge 6 $.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 5-11
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Cospectral Pairs of Regular Graphs with Different Connectivity
Autorzy:
Haemers, Willem H.
Powiązania:
https://bibliotekanauki.pl/articles/31552242.pdf
Data publikacji:
2020-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph spectrum
vertex-connectivity
edge-connectivity
spectral characterization
Opis:
For vertex- and edge-connectivity we construct infinitely many pairs of regular graphs with the same spectrum, but with different connectivity.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 2; 577-584
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Sharp Lower Bound For The Generalized 3-Edge-Connectivity Of Strong Product Graphs
Autorzy:
Sun, Yuefang
Powiązania:
https://bibliotekanauki.pl/articles/31341589.pdf
Data publikacji:
2017-11-27
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
generalized connectivity
generalized edge-connectivity
strong product
Opis:
The generalized $k$-connectivity $ \kappa_k (G) $ of a graph $G$, mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$-edge-connectivity which is defined as $ \lambda_k (G) = \text{min} \{ \lambda_G (S) | S \subseteq V (G) $ and $ |S| = k \} $, where $ \lambda_G (S) $ denote the maximum number $ \mathcal{l} $ of pairwise edge-disjoint trees $ T_1 $, $ T_2 $, . . ., $ T_\mathcal{l} $ in $G$ such that $S \subseteq V (T_i)$ for $ 1 \le i \le \mathcal{l} $. In this paper we get a sharp lower bound for the generalized 3-edge-connectivity of the strong product of any two connected graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 4; 975-988
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs with Large Generalized (Edge-)Connectivity
Autorzy:
Li, Xueliang
Mao, Yaping
Powiązania:
https://bibliotekanauki.pl/articles/31340594.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
(edge-)connectivity
Steiner tree
internally disjoint trees
edge-disjoint trees
packing
generalized (edge-)connectivity
Opis:
The generalized $k$-connectivity $ \kappa_k (G) $ of a graph $G$, introduced by Hager in 1985, is a nice generalization of the classical connectivity. Recently, as a natural counterpart, we proposed the concept of generalized $k$-edge-connectivity $ \lambda_k (G)$. In this paper, graphs of order $n$ such that $ \kappa_k (G) = n - k/2 - 1 $ and $ \lambda_k (G) = n - k/2 - 1 $ for even $k$ are characterized.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 931-958
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Arc Fault Tolerance of Cartesian Product of Regular Digraphs on Super-Restricted Arc-Connectivity
Autorzy:
Zhang, Guozhen
Wang, Shiying
Powiązania:
https://bibliotekanauki.pl/articles/31343704.pdf
Data publikacji:
2019-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
fault tolerance
restricted arc-connectivity
super-restricted arc- connectivity
Cartesian product
regular digraph
Opis:
Let $ D = (V (D),A(D)) $ be a strongly connected digraph. An arc set $ S \subseteq A(D) $ is a restricted arc-cut of $D$ if $ D − S$ has a non-trivial strong component $ D_1 $ such that $ D − V (D_1)$ contains an arc. The restricted arc-connectivity $ \lambda^‘(D) $ is the minimum cardinality over all restricted arc-cuts of $D$. In [C. Balbuena, P. García-Vázquez, A. Hansberg and L.P. Montejano, On the super-restricted arc-connectivity of s-geodetic digraphs, Networks 61 (2013) 20-28], Balbuena et al. introduced the concept of super-$ \lambda^' $ digraphs. In this paper, we first introduce the concept of the arc fault tolerance of a digraph $D$ on the super-$ \lambda^‘ $ property. We define a super-$ \lambda^′ $ digraph $D$ to be $m$-super-$ \lambda^‘ $ if $D − S $ is still super-$ \lambda^‘ $ for any $ S \subseteq A(D) $ with $ |S| \le m $. The maximum value of such $m$, denoted by $S_{ \lambda^’ } (D) $, is said to be the arc fault tolerance of $D$ on the super-$ \lambda^‘$ property. $ S_{ \lambda^’ } (D) $ is an index to measure the reliability of networks. Next we provide a necessary and sufficient condition for the Cartesian product of regular digraphs to be super-$ \lambda^‘ $. Finally, we give the lower and upper bounds on $ S_{ \lambda^’ } (D) $ for the Cartesian product $D$ of regular digraphs and give an example to show that the lower and upper bounds are best possible. In particular, the exact value of $ S_{ \lambda^’ } (D) $ is obtained in special cases.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 95-116
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A proof of mengers theorem by contraction
Autorzy:
Göring, Frank
Powiązania:
https://bibliotekanauki.pl/articles/743549.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
connectivity
disjoint paths
digraph
Menger
Opis:
A short proof of the classical theorem of Menger concerning the number of disjoint AB-paths of a finite graph for two subsets A and B of its vertex set is given. The main idea of the proof is to contract an edge of the graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 111-112
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The connectivity of domination dot-critical graphs with no critical vertices
Autorzy:
Furuya, Michitaka
Powiązania:
https://bibliotekanauki.pl/articles/30148712.pdf
Data publikacji:
2014-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dot-critical graph
critical vertex
connectivity
Opis:
An edge of a graph is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. A vertex of a graph is called critical if its deletion decreases the domination number. In A note on the domination dot-critical graphs, Discrete Appl. Math. 157 (2009) 3743-3745, Chen and Shiu constructed for each even integer k ≥ 4 infinitely many k-dot-critical graphs G with no critical vertices and κ(G) = 1. In this paper, we refine their result and construct for integers k ≥ 4 and l ≥ 1 infinitely many k-dot-critical graphs G with no critical vertices, κ(G) = 1 and λ(G) = l. Furthermore, we prove that every 3-dot- critical graph with no critical vertices is 3-connected, and it is best possible.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 4; 683-690
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds for the rainbow connection number of graphs
Autorzy:
Schiermeyer, Ingo
Powiązania:
https://bibliotekanauki.pl/articles/743926.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow colouring
rainbow connectivity
extremal problem
Opis:
An edge-coloured graph G is rainbow-connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow-connected. In this paper we show some new bounds for the rainbow connection number of graphs depending on the minimum degree and other graph parameters. Moreover, we discuss sharpness of some of these bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 2; 387-395
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Sharp Upper Bounds for Generalized Edge-Connectivity of Product Graphs
Autorzy:
Sun, Yuefang
Powiązania:
https://bibliotekanauki.pl/articles/31340760.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
generalized edge-connectivity
Cartesian product
strong product
lexicographic product
Opis:
The generalized $k$-connectivity $ \kappa_k (G) $ of a graph $G$ was introduced by Hager in 1985. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$-edge-connectivity which is defined as $ \lambda k(G) = \text{min} \{ \lambda (S) : S \subseteq V (G) \text{ and } |S| = k \} $, where $ \lambda(S) $ denote the maximum number $ \mathcal{l} $ of pairwise edge-disjoint trees $ T_1, T_2, . . ., T_\mathcal{l} $ in $G$ such that $ S \subseteq V ( T_i ) $ for $ 1 \le i \le \mathcal{l} $. In this paper, we study the generalized edge- connectivity of product graphs and obtain sharp upper bounds for the generalized 3-edge-connectivity of Cartesian product graphs and strong product graphs. Among our results, some special cases are also discussed.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 833-843
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 42

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies