Temat: arbitrarily vertex decomposable - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: A note of arbitrarily vertex decomposable graphs
Autorzy:: Marczyk, A.
Powiązania:: https://bibliotekanauki.pl/articles/254919.pdf
Data publikacji:: 2006
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: arbitrarily vertex decomposable graphs
traceable graphs
independence number
perfect matching
Opis:: A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n1,..., nk) of positive integers such that n1 + ... + nk = n there exists a partition (V1,..., Vk) of the vertex set of G such that for each i ∈ {1,..., k}, Vi induces a connected subgraph of G on ni vertices. In this paper we show that if G is a two-connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n - 3, then G is arbitrarily vertex decomposable. We present another result for connected graphs satisfying a similar condition, where the bound n - 3 is replaced by n - 2.
Źródło:: Opuscula Mathematica; 2006, 26, 1; 109-118
1232-9274
2300-6919
Pojawia się w:: Opuscula Mathematica
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Arbitrarily Partitionable {2K₂, C₄}-Free Graphs
Autorzy:: Liu, Fengxia
Wu, Baoyindureng
Meng, Jixiang
Powiązania:: https://bibliotekanauki.pl/articles/32361721.pdf
Data publikacji:: 2022-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: arbitrarily partitionable graphs
arbitrarily vertex decomposable
threshold graphs
{2 K 2, C 4 }-free graphs
Opis:: A graph G = (V, E) of order n is said to be arbitrarily partitionable if for each sequence λ = (λ₁, λ₂, …, λ_p) of positive integers with λ₁ + … +λ_p = n, there exists a partition (V₁, V₂, … , V_p) of the vertex set V such that V_i induces a connected subgraph of order λ_i in G for each i ∈ {1, 2, …, p}. In this paper, we show that a threshold graph is arbitrarily partitionable if and only if it admits a perfect matching or a near perfect matching. We also give a necessary and sufficient condition for a {2K₂, C₄}-free graph being arbitrarily partitionable, as an extension for a result of Broersma, Kratsch and Woeginger [Fully decomposable split graphs, European J. Combin. 34 (2013) 567–575] on split graphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2022, 42, 2; 485-500
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: Arbitrarily vertex decomposable caterpillars with four or five leaves
Autorzy:: Cichacz, Sylwia
Görlich, Agnieszka
Marczyk, Antoni
Przybyło, Jakub
Woźniak, Mariusz
Powiązania:: https://bibliotekanauki.pl/articles/743967.pdf
Data publikacji:: 2006
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: arbitrarily vertex decomposable graphs
trees
caterpillars
star-like trees
Opis:: A graph G of order n is called arbitrarily vertex decomposable if for each sequence (a₁,...,aₖ) of positive integers such that a₁+...+aₖ = n there exists a partition (V₁,...,Vₖ) of the vertex set of G such that for each i ∈ {1,...,k}, $V_i$ induces a connected subgraph of G on $a_i$ vertices. D. Barth and H. Fournier showed that if a tree T is arbitrarily vertex decomposable, then T has maximum degree at most 4. In this paper we give a complete characterization of arbitrarily vertex decomposable caterpillars with four leaves. We also describe two families of arbitrarily vertex decomposable trees with maximum degree three or four.
Źródło:: Discussiones Mathematicae Graph Theory; 2006, 26, 2; 291-305
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: On arbitrarily vertex decomposable unicyclic graphs with dominating cycle
Autorzy:: Cichacz, Sylwia
Zioło, Irmina
Powiązania:: https://bibliotekanauki.pl/articles/743581.pdf
Data publikacji:: 2006
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: arbitrarily vertex decomposable graph
dominating cycle
Opis:: A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,...,nₖ) of positive integers such that $∑^k_{i=1} n_i = n$, there exists a partition (V₁,...,Vₖ) of vertex set of G such that for every i ∈ {1,...,k} the set $V_i$ induces a connected subgraph of G on $n_i$ vertices. We consider arbitrarily vertex decomposable unicyclic graphs with dominating cycle. We also characterize all such graphs with at most four hanging vertices such that exactly two of them have a common neighbour.
Źródło:: Discussiones Mathematicae Graph Theory; 2006, 26, 3; 403-412
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 5.

Tytuł:: On some families of arbitrarily vertex decomposable spiders
Autorzy:: Juszczyk, T.
Zioło, I. A.
Powiązania:: https://bibliotekanauki.pl/articles/254779.pdf
Data publikacji:: 2010
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: arbitrarily vertex decomposable graph
trees
Opis:: A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n1, . . . , nk) of positive integers such that [formula], there exists a partition (V1, . . . , Vk) of the vertex set of G such that for every i ∈ {1, . . . , k} the set Vi induces a connected subgraph of G on ni vertices. A spider is a tree with one vertex of degree at least 3. We characterize two families of arbitrarily vertex decomposable spiders which are homeomorphic to stars with at most four hanging edges.
Źródło:: Opuscula Mathematica; 2010, 30, 2; 147-154
1232-9274
2300-6919
Pojawia się w:: Opuscula Mathematica
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 6.

Tytuł:: Recursively arbitrarily vertex-decomposable suns
Autorzy:: Baudon, O.
Gilbert, F.
Woźniak, M.
Powiązania:: https://bibliotekanauki.pl/articles/254835.pdf
Data publikacji:: 2011
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: arbitrarily vertex-decomposable graphs (AVD)
recursively AVD graphs
Opis:: A graph G = (V,E) is arbitrarily vertex decomposable if for any sequence τ of positive integers adding up to /V /, there is a sequence of vertex-disjoint subsets of V whose orders are given by τ , and which induce connected graphs. The aim of this paper is to study the recursive version of this problem on a special class of graphs called suns. This paper is a complement of [O. Baudon, F. Gilbert, M. Woźniak, Recursively arbitrarily vertex-decomposable graphs, research report, 2010].
Źródło:: Opuscula Mathematica; 2011, 31, 4; 533-547
1232-9274
2300-6919
Pojawia się w:: Opuscula Mathematica
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja