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: 12

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  connectivity
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Connectivity of path graphs

100%
Knor M., Niepel L. u.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 2
181-195
EN
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.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A proof of menger's theorem by contraction

100%
Göring F.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
111-112
EN
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.
3
Content available remote

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

100%
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.
4
Content available remote

On the connectivity of efficient point sets

100%
Song W.
Applicationes Mathematicae
|
1998-1999
|
tom 25
|
nr 1
121-127
EN
The connectivity of the efficient point set and of some proper efficient point sets in locally convex spaces is investigated.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Ordered and linked chordal graphs

100%
Böhme T., Gerlach T., Stiebitz M.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 2
367-373
EN
A graph G is called k-ordered if for every sequence of k distinct vertices there is a cycle traversing these vertices in the given order. In the present paper we consider two novel generalizations of this concept, k-vertex-edge-ordered and strongly k-vertex-edge-ordered. We prove the following results for a chordal graph G: (a) G is (2k-3)-connected if and only if it is k-vertex-edge-ordered (k ≥ 3). (b) G is (2k-1)-connected if and only if it is strongly k-vertex-edge-ordered (k ≥ 2). (c) G is k-linked if and only if it is (2k-1)-connected.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Edge-connectivity of strong products of graphs

100%
Bresar B., Spacapan S.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 2
333-343
EN
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.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Edge-disjoint paths in permutation graphs

88%
Gopalakrishnan C., Pandu Rangan C.
Discussiones Mathematicae Graph Theory
|
1995
|
tom 15
|
nr 1
59-72
EN
In this paper we consider the following problem. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two edge-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂, respectively. We give a linear (O(|V|+|E|)) algorithm to solve this problem on a permutation graph.
8
Content available remote

Large Degree Vertices in Longest Cycles of Graphs, I

88%
Li B., Xiong L., Yin J.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
363-382
EN
In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d.
9
Content available remote

The Vertex-Rainbow Index of A Graph

88%
Mao Y.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
669-681
EN
The k-rainbow index rxk(G) of a connected graph G was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the k-rainbow index, we introduce the concept of k-vertex-rainbow index rvxk(G) in this paper. In this paper, sharp upper and lower bounds of rvxk(G) are given for a connected graph G of order n, that is, 0 ≤ rvxk(G) ≤ n − 2. We obtain Nordhaus-Gaddum results for 3-vertex-rainbow index of a graph G of order n, and show that rvx3(G) + rvx3(Ḡ) = 4 for n = 4 and 2 ≤ rvx3(G) + rvx3(Ḡ) ≤ n − 1 for n ≥ 5. Let t(n, k, ℓ) denote the minimal size of a connected graph G of order n with rvxk(G) ≤ ℓ, where 2 ≤ ℓ ≤ n − 2 and 2 ≤ k ≤ n. Upper and lower bounds on t(n, k, ℓ) are also obtained.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Chvátal-Erdos condition and pancyclism

88%
Flandrin E., Li H., Marczyk A., Schiermeyer I., Woźniak M.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 2
335-342
EN
The well-known Chvátal-Erdős theorem states that if the stability number α of a graph G is not greater than its connectivity then G is hamiltonian. In 1974 Erdős showed that if, additionally, the order of the graph is sufficiently large with respect to α, then G is pancyclic. His proof is based on the properties of cycle-complete graph Ramsey numbers. In this paper we show that a similar result can be easily proved by applying only classical Ramsey numbers.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A linear algorithm for the two paths problem on permutation graphs

75%
Gopalakrishnan C., Pandu Rangan C.
Discussiones Mathematicae Graph Theory
|
1995
|
tom 15
|
nr 2
147-166
EN
The 'two paths problem' is stated as follows. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two vertex-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂ respectively. In this paper we give a linear (O(|V|+ |E|)) algorithm to solve the above problem on a permutation graph.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Intersection graph of gamma sets in the total graph

75%
Chelvam T., Asir T.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 2
341-356
EN
In this paper, we consider the intersection graph $I_{Γ}(ℤₙ)$ of gamma sets in the total graph on ℤₙ. We characterize the values of n for which $I_{Γ}(ℤₙ)$ is complete, bipartite, cycle, chordal and planar. Further, we prove that $I_{Γ}(ℤₙ)$ is an Eulerian, Hamiltonian and as well as a pancyclic graph. Also we obtain the value of the independent number, the clique number, the chromatic number, the connectivity and some domination parameters of $I_{Γ}(ℤₙ)$.
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ć.