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

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-11 z 11
    Tytuł:
    Minimum Edge Cuts in Diameter 2 Graphs
    Autorzy:
    Bickle, Allan
    Schwenk, Allen
    Powiązania:
    https://bibliotekanauki.pl/articles/31343375.pdf
    Data publikacji:
    2019-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge connectivity
    diameter
    Opis:
    Plesnik proved that the edge connectivity and minimum degree are equal for diameter 2 graphs. We provide a streamlined proof of this fact and characterize the diameter 2 graphs with a nontrivial minimum edge cut.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2019, 39, 2; 605-608
    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ł:
    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ł:
    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ł:
    More on even [a,b]-factors in graphs
    Autorzy:
    Khodkar, Abdollah
    Xu, Rui
    Powiązania:
    https://bibliotekanauki.pl/articles/743747.pdf
    Data publikacji:
    2007
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    [a,b]-factor
    spanning graph
    edge-connectivity
    Opis:
    In this note we give a characterization of the complete bipartite graphs which have an even (odd) [a,b]-factor. For general graphs we prove that an a-edge connected graph G with n vertices and with δ(G) ≥ max{a+1,an/(a+b) + a - 2} has an even [a,b]-factor, where a and b are even and 2 ≤ a ≤ b. With regard to the edge-connectivity this result is slightly better than one of the similar results obtained by Kouider and Vestergaard in 2004 and unlike their results, this result has no restriction on the order of graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2007, 27, 1; 193-204
    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ł:
    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ł
    Tytuł:
    Sufficient Conditions for Maximally Edge-Connected and Super-Edge-Connected Graphs Depending on The Clique Number
    Autorzy:
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/31343389.pdf
    Data publikacji:
    2019-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge-connectivity
    clique number
    maximally edge-connected graphs
    super-edge-connected graphs
    Opis:
    Let G be a connected graph with minimum degree δ and edge-connectivity λ. A graph is maximally edge-connected if λ = δ, and it is super-edgeconnected if every minimum edge-cut is trivial; that is, if every minimum edge-cut consists of edges incident with a vertex of minimum degree. The clique number ω(G) of a graph G is the maximum cardinality of a complete subgraph of G. In this paper, we show that a connected graph G with clique number ω(G) ≤ r is maximally edge-connected or super-edge-connected if the number of edges is large enough. These are generalizations of corresponding results for triangle-free graphs by Volkmann and Hong in 2017.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2019, 39, 2; 567-573
    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ł:
    More on the Rainbow Disconnection in Graphs
    Autorzy:
    Bai, Xuqing
    Chang, Renying
    Huang, Zhong
    Li, Xueliang
    Powiązania:
    https://bibliotekanauki.pl/articles/32222544.pdf
    Data publikacji:
    2022-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge-coloring
    edge-connectivity
    rainbow disconnection coloring (number)
    Erdős-Gallai type problem
    Nordhaus-Gaddum type bounds
    complexity
    NP-hard (complete)
    Opis:
    Let G be a nontrivial edge-colored connected graph. An edge-cut R of G is called a rainbow-cut if no two of its edges are colored the same. An edge-colored graph G is rainbow disconnected if for every two vertices u and v of G, there exists a u-v-rainbow-cut separating them. For a connected graph G, the rainbow disconnection number of G, denoted by rd(G), is defined as the smallest number of colors that are needed in order to make G rainbow disconnected. In this paper, we first determine the maximum size of a connected graph G of order n with rd(G) = k for any given integers k and n with 1 ≤ k ≤ n − 1, which solves a conjecture posed only for n odd in [G. Chartrand, S. Devereaux, T.W. Haynes, S.T. Hedetniemi and P. Zhang, Rainbow disconnection in graphs, Discuss. Math. Graph Theory 38 (2018) 1007–1021]. From this result and a result in their paper, we obtain Erdős-Gallai type results for rd(G). Secondly, we discuss bounds on rd(G) for complete multipartite graphs, critical graphs with respect to the chromatic number, minimal graphs with respect to the chromatic index, and regular graphs, and we also give the values of rd(G) for several special graphs. Thirdly, we get Nordhaus-Gaddum type bounds for rd(G), and examples are given to show that the upper and lower bounds are sharp. Finally, we show that for a connected graph G, to compute rd(G) is NP-hard. In particular, we show that it is already NP-complete to decide if rd(G) = 3 for a connected cubic graph. Moreover, we show that for a given edge-colored (with an unbounded number of colors) connected graph G it is NP-complete to decide whether G is rainbow disconnected.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1185-1204
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The Gutman Index and the Edge-Wiener Index of Graphs with Given Vertex-Connectivity
    Autorzy:
    Mazorodze, Jaya Percival
    Mukwembi, Simon
    Vetrík, Tomáš
    Powiązania:
    https://bibliotekanauki.pl/articles/31340463.pdf
    Data publikacji:
    2016-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Gutman index
    edge-Wiener index
    vertex-connectivity
    Opis:
    The Gutman index and the edge-Wiener index have been extensively investigated particularly in the last decade. An important stream of re- search on graph indices is to bound indices in terms of the order and other parameters of given graph. In this paper we present asymptotically sharp upper bounds on the Gutman index and the edge-Wiener index for graphs of given order and vertex-connectivity κ, where κ is a constant. Our results substantially generalize and extend known results in the area.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 4; 867-876
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-11 z 11

      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