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

Wyszukiwano:
w słowach kluczowych:  minimum degree
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

Vertex-disjoint stars in graphs

100%
Ota K.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 2
179-185
EN
In this paper, we give a sufficient condition for a graph to contain vertex-disjoint stars of a given size. It is proved that if the minimum degree of the graph is at least k+t-1 and the order is at least (t+1)k + O(t²), then the graph contains k vertex-disjoint copies of a star $K_{1,t}$. The condition on the minimum degree is sharp, and there is an example showing that the term O(t²) for the number of uncovered vertices is necessary in a sense.
2
Content available remote

On the Rainbow Vertex-Connection

100%
Li X., Shi Y.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
307-313
EN
A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertexconnected. It was proved that if G is a graph of order n with minimum degree δ, then rvc(G) < 11n/δ. In this paper, we show that rvc(G) ≤ 3n/(δ+1)+5 for [xxx] and n ≥ 290, while rvc(G) ≤ 4n/(δ + 1) + 5 for [xxx] and rvc(G) ≤ 4n/(δ + 1) + C(δ) for 6 ≤ δ ≤ 15, where [xxx]. We also prove that rvc(G) ≤ 3n/4 − 2 for δ = 3, rvc(G) ≤ 3n/5 − 8/5 for δ = 4 and rvc(G) ≤ n/2 − 2 for δ = 5. Moreover, an example constructed by Caro et al. shows that when [xxx] and δ = 3, 4, 5, our bounds are seen to be tight up to additive constants.
3
Content available remote

A Degree Condition Implying Ore-Type Condition for Even [2,b]-Factors in Graphs

100%
Tsuchiya S., Yashima T.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
797-809
EN
For a graph G and even integers b ⩾ a ⩾ 2, a spanning subgraph F of G such that a ⩽ degF (x) ⩽ b and degF (x) is even for all x ∈ V (F) is called an even [a, b]-factor of G. In this paper, we show that a 2-edge-connected graph G of order n has an even [2, b]-factor if [...] max {degG (x),degG (y)}⩾max {2n2+b,3} $\max \{ \deg _G (x),\deg _G (y)\} \ge \max \left\{ {{{2n} \over {2 + b}},3} \right\}$ for any nonadjacent vertices x and y of G. Moreover, we show that for b ⩾ 3a and a > 2, there exists an infinite family of 2-edge-connected graphs G of order n with δ(G) ⩾ a such that G satisfies the condition [...] degG (x)+degG (y)>2ana+b $\deg _G (x) + \deg _G (y) > {{2an} \over {a + b}}$ for any nonadjacent vertices x and y of G, but has no even [a, b]-factors. In particular, the infinite family of graphs gives a counterexample to the conjecture of Matsuda on the existence of an even [a, b]-factor.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Vertex-disjoint copies of K¯₄

100%
Kawarabayashi K.-i.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
249-262
EN
Let G be a graph of order n. Let K¯ₗ be the graph obtained from Kₗ by removing one edge. In this paper, we propose the following conjecture: Let G be a graph of order n ≥ lk with δ(G) ≥ (n-k+1)(l-3)/(l-2)+k-1. Then G has k vertex-disjoint K¯ₗ. This conjecture is motivated by Hajnal and Szemerédi's [6] famous theorem. In this paper, we verify this conjecture for l=4.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Triangle-free planar graphs with minimum degree 3 have radius at least 3

88%
Kim S.-J., West D.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 3
563-566
EN
We prove that every triangle-free planar graph with minimum degree 3 has radius at least 3; equivalently, no vertex neighborhood is a dominating set.
6
Content available remote

A Neighborhood Condition for Fractional ID-[A, B]-Factor-Critical Graphs

75%
Zhou S., Yang F., Sun Z.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
409-418
EN
Let G be a graph of order n, and let a and b be two integers with 1 ≤ a ≤ b. Let h : E(G) → [0, 1] be a function. If a ≤ ∑e∋x h(e) ≤ b holds for any x ∈ V (G), then we call G[Fh] a fractional [a, b]-factor of G with indicator function h, where Fh = {e ∈ E(G) : h(e) > 0}. A graph G is fractional independent-set-deletable [a, b]-factor-critical (in short, fractional ID-[a, b]- factor-critical) if G − I has a fractional [a, b]-factor for every independent set I of G. In this paper, it is proved that if [...] for any two nonadjacent vertices x, y ∈ V (G), then G is fractional ID-[a, b]-factor-critical. Furthermore, it is shown that this result is best possible in some sense.
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ć.