Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 6

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

A Sufficient Condition for Graphs to Be SuperK-Restricted Edge Connected

100%
Wang S., Wang M., Zhang L.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
537-545
EN
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 λk(G), is defined as the cardinality of a minimum k-restricted edge cut. Let ξk(G) = min{|[X, X̄]| : |X| = k, G[X] is connected}, where X̄ = V (G)\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 ν ≥ 2k. In this paper, we show that if |N(u) ∩ N(v)| ≥ k +1 for all pairs u, v of nonadjacent vertices and [...] ξk(G)≤⌊ν2⌋+k $\xi _k (G) \le \left\lfloor {{\nu \over 2}} \right\rfloor + k$ , then G is super k-restricted edge connected.
2
Content available remote

On the Maximum and Minimum Sizes of a Graph with Givenk-Connectivity

81%
Sun Y.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
623-632
EN
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.
3
Content available remote

Rainbow Connection Number of Graphs with Diameter 3

81%
Li H., Li X., Sun Y.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
141-154
EN
A path in an edge-colored graph G is rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest integer k for which there exists a k-edge-coloring of G such that every pair of distinct vertices of G is connected by a rainbow path. Let f(d) denote the minimum number such that rc(G) ≤ f(d) for each bridgeless graph G with diameter d. In this paper, we shall show that 7 ≤ f(3) ≤ 9.
4
Content available remote

Characterizing Atoms that Result from Decomposition by Clique Separators

62%
McKee T. A.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
587-594
EN
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. Atoms are characterized here in two ways: first using generalized vertex elimination schemes, and then as generalizations of 2-connected unichord-free graphs (the graphs in which every minimal vertex separator induces an edgeless subgraph).
5
Content available remote

On Two Generalized Connectivities of Graphs

62%
Sun Y., Li F., Jin Z.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
245-261
EN
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. The pendant tree-connectivity τ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 κ′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 κ′k(G) and τk(G) by showing that for a connected graph G of order n, if κ′k(G) ≠ n − k + 1 where k ≥ 3, then 1 ≤ κ′k(G) − τk(G) ≤ n − k; otherwise, 1 ≤ κ′k(G) ‘− τk(G) ≤ 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 τk(G), where G is a cubic or 4-regular Cayley graph on Abelian groups, 3 ≤ k ≤ n.
6
Content available remote

Rainbow Vertex-Connection and Forbidden Subgraphs

52%
Li W., Li X., Zhang J.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
143-154
EN
A path in a vertex-colored graph is called vertex-rainbow if its internal vertices have pairwise distinct colors. A vertex-colored graph G is rainbow vertex-connected if for any two distinct vertices of G, there is a vertex-rainbow path connecting them. For a connected graph G, the rainbow vertex-connection number of G, denoted by rvc(G), is defined as the minimum number of colors that are required to make G rainbow vertex-connected. In this paper, we find all the families ℱ of connected graphs with |ℱ| ∈ {1, 2}, for which there is a constant kℱ such that, for every connected ℱ-free graph G, rvc(G) ≤ diam(G) + kℱ, where diam(G) is the diameter of G.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.