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ę "k -connectivity" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-7 z 7
    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ł:
    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ł:
    Separation of Cartesian Products of Graphs Into Several Connected Components by the Removal of Vertices
    Autorzy:
    Erker, Tjaša Paj
    Špacapan, Simon
    Powiązania:
    https://bibliotekanauki.pl/articles/32304144.pdf
    Data publikacji:
    2022-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    k -connectivity
    Cartesian product
    Opis:
    A set S ⊆ V (G) is a vertex k-cut in a graph G = (V (G), E(G)) if G − S has at least k connected components. The k-connectivity of G, denoted as κk(G), is the minimum cardinality of a vertex k-cut in G. We give several constructions of a set S such that (G□H) − S has at least three connected components. Then we prove that for any 2-connected graphs G and H, of order at least six, one of the defined sets S is a minimum vertex 3-cut in G□H. This yields a formula for κ3(G□H).
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 3; 905-920
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Minimally Strong Subgraph (k, ℓ)-Arc-Connected Digraphs
    Autorzy:
    Sun, Yuefang
    Jin, Zemin
    Powiązania:
    https://bibliotekanauki.pl/articles/32304302.pdf
    Data publikacji:
    2022-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    strong subgraph k -connectivity
    strong subgraph k -arc-connectivity
    subdigraph packing
    Opis:
    Let $D = (V,A)$ be a digraph of order $n$, $S$ a subset of $V$ of size $k$ and $ 2 \le k \le n$. A subdigraph $H$ of $D$ is called an $S$-strong subgraph if $H$ is strong and $ S \subseteq V (H) $. Two $S$-strong subgraphs $ D_1 $ and $ D_2 $ are said to be arc-disjoint if $ A(D_1) \cap A(D_2) = \emptyset $. Let $ \lambda_S (D) $ be the maximum number of arc-disjoint $S$-strong digraphs in $D$. The strong subgraph $k$-arc-connectivity is defined as $ \lambda_k (D) = \text{min} \{ \lambda_S (D) | S \subseteq V, |S| = k \} $. A digraph $ D = (V, A) $ is called minimally strong subgraph $ (k, \mathcal{l})$-arc-connected if $ \lambda_k (D) \ge \mathcal{l} $ but for any arc $ e \in A $, $ \lambda_k(D − e) \le \mathcal{l} − 1 $. Let \( \mathfrak{G}(n, k, \mathscr{l} ) \) be the set of all minimally strong subgraph $ (k, \mathcal{l} )$-arc-connected digraphs with order $n$. We define $ G(n, k, \mathcal{l} ) = $ \( \max \{ |A(D)| \ | D \in \mathfrak{G} (n, k, \mathcal{l} ) \} \) and $ g(n, k, \mathcal{l} ) = $ \( \min \{ |A(D)| \ | D \in \mathfrak{G}(n, k, \mathcal{l} ) \} \). In this paper, we study the minimally strong subgraph $ (k, \mathcal{l} ) $-arc-connected digraphs. We give a characterization of the minimally strong sub-graph $ (3, n − 2) $-arc-connected digraphs, and then give exact values and bounds for the functions $ g(n, k, \mathcal{l} )$ and $ G(n, k, \mathcal{l} ) $.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 3; 759-770
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On Two Generalized Connectivities of Graphs
    Autorzy:
    Sun, Yuefang
    Li, Fengwei
    Jin, Zemin
    Powiązania:
    https://bibliotekanauki.pl/articles/31342427.pdf
    Data publikacji:
    2018-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    k -connectivity
    pendant tree-connectivity
    Cartesian product
    Cayley graph
    Opis:
    The concept of generalized $k$-connectivity $ \kappa_k (G) $, mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. The pendant tree-connectivity $ \tau_k (G) $ was also introduced by Hager in 1985, which is a specialization of generalized $k$-connectivity but a generalization of the classical connectivity. Another generalized connectivity of a graph $G$, named $k$-connectivity $ \kappa_k^' (G) $, introduced by Chartrand et al. in 1984, is a generalization of the cut-version of the classical connectivity. In this paper, we get the lower and upper bounds for the difference of $ \kappa_k^' (G) $ and $ \tau_k(G) $ by showing that for a connected graph $G$ of order $n$, if $ \kappa_k^' (G) \ne n − k + 1 $ where $ k \ge 3 $, then $ 1 \le \kappa_k^' (G) − \tau_k (G) \le n − k $; otherwise, $ 1 \le κ_k^' (G) − \tau_k(G) \le n − k + 1 $. Moreover, all of these bounds are sharp. We get a sharp upper bound for the 3-connectivity of the Cartesian product of any two connected graphs with orders at least 5. Especially, the exact values for some special cases are determined. Among our results, we also study the pendant tree-connectivity of Cayley graphs on Abelian groups of small degrees and obtain the exact values for $ \tau_k(G) $, where $G$ is a cubic or 4-regular Cayley graph on Abelian groups, $ 3 \le k \le n $.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 1; 245-261
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A Sufficient Condition for Graphs to Be Super k-Restricted Edge Connected
    Autorzy:
    Wang, Shiying
    Wang, Meiyu
    Zhang, Lei
    Powiązania:
    https://bibliotekanauki.pl/articles/31341790.pdf
    Data publikacji:
    2017-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph
    neighborhood
    k -restricted edge connectivity
    super k -restricted edge connected graph
    Opis:
    For a subset $S$ of edges in a connected graph $G$, $S$ is a $k$-restricted edge cut if $G − S$ is disconnected and every component of $G − S$ has at least $k$ vertices. The $k$-restricted edge connectivity of $G$, denoted by $ \lambda_k (G) $, is defined as the cardinality of a minimum $k$-restricted edge cut. Let \( \xi_k(G) = \text{min} \{ | [ X , \overline{X} ] | : |X| = k, G[X] \) is connected $ \} $, where $ \overline{X} = V (G) \backslash X $. A graph $G$ is super $k$-restricted edge connected if every minimum $k$-restricted edge cut of $G$ isolates a component of order exactly $k$. Let $k$ be a positive integer and let $G$ be a graph of order $ \nu \ge 2k$. In this paper, we show that if $ | N( u ) \cup N( v ) | \ge k +1 $ for all pairs $u$, $v$ of nonadjacent vertices and $ \xi_k (G) \le \floor{ ν/2}+k $, then $G$ is super $k$-restricted edge connected.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 3; 537-545
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Independence Number, Connectivity and All Fractional (a, b, k)-Critical Graphs
    Autorzy:
    Yuan, Yuan
    Hao, Rong-Xia
    Powiązania:
    https://bibliotekanauki.pl/articles/31343586.pdf
    Data publikacji:
    2019-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    independence number
    connectivity
    fractional [a
    b]-factor
    frac- tional (a
    b
    k)-critical graph
    all fractional (a
    Opis:
    Let $G$ be a graph and $a$, $b$ and $k$ be nonnegative integers with $ 1 \le a \le b $. A graph $G$ is defined as all fractional $(a, b, k)$-critical if after deleting any $k$ vertices of $G$, the remaining graph has all fractional $[a, b]$-factors. In this paper, we prove that if \( \kappa(G) \ge \text{max} \{ \tfrac{(b+1)^2+2k}{2}, \tfrac{(b+1)^2 \alpha(G)+4ak}{4a} \} \), then $G$ is all fractional $(a, b, k)$-critical. If $k = 0$, we improve the result given in [Filomat 29 (2015) 757-761]. Moreover, we show that this result is best possible in some sense.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2019, 39, 1; 183-190
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-7 z 7

      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