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

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
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On non-z(mod k) dominating sets

100%
Caro Y., Jacobson M.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 1
189-199
EN
For a graph G, a positive integer k, k ≥ 2, and a non-negative integer with z < k and z ≠ 1, a subset D of the vertex set V(G) is said to be a non-z (mod k) dominating set if D is a dominating set and for all x ∈ V(G), |N[x]∩D| ≢ z (mod k).For the case k = 2 and z = 0, it has been shown that these sets exist for all graphs. The problem for k ≥ 3 is unknown (the existence for even values of k and z = 0 follows from the k = 2 case.) It is the purpose of this paper to show that for k ≥ 3 and with z < k and z ≠ 1, that a non-z(mod k) dominating set exist for all trees. Also, it will be shown that for k ≥ 4, z ≥ 1, 2 or 3 that any unicyclic graph contains a non-z(mod k) dominating set. We also give a few special cases of other families of graphs for which these dominating sets must exist.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Destroying symmetry by orienting edges: complete graphs and complete bigraphs

100%
Harary F., Jacobson M.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 2
149-158
EN
Our purpose is to introduce the concept of determining the smallest number of edges of a graph which can be oriented so that the resulting mixed graph has the trivial automorphism group. We find that this number for complete graphs is related to the number of identity oriented trees. For complete bipartite graphs $K_{s,t}$, s ≤ t, this number does not always exist. We determine for s ≤ 4 the values of t for which this number does exist.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Generalized ramsey theory and decomposable properties of graphs

81%
Burr S., Jacobson M., Mihók P., Semanišin G.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
199-217
EN
In this paper we translate Ramsey-type problems into the language of decomposable hereditary properties of graphs. We prove a distributive law for reducible and decomposable properties of graphs. Using it we establish some values of graph theoretical invariants of decomposable properties and show their correspondence to generalized Ramsey numbers.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On a conjecture of quintas and arc-traceability in upset tournaments

81%
Busch A., Jacobson M., Reid K.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 3
225-239
EN
A digraph D = (V,A) is arc-traceable if for each arc xy in A, xy lies on a directed path containing all the vertices of V, i.e., hamiltonian path. We prove a conjecture of Quintas [7]: if D is arc-traceable, then the condensation of D is a directed path. We show that the converse of this conjecture is false by providing an example of an upset tournament which is not arc-traceable. We then give a characterization for upset tournaments in terms of their score sequences, characterize which arcs of an upset tournament lie on a hamiltonian path, and deduce a characterization of arc-traceable upset tournaments.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Potential forbidden triples implying hamiltonicity: for sufficiently large graphs

81%
Faudree R., Gould R., Jacobson M.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 3
273-289
EN
In [1], Brousek characterizes all triples of connected graphs, G₁,G₂,G₃, with $G_i = K_{1,3}$ for some i = 1,2, or 3, such that all G₁G₂ G₃-free graphs contain a hamiltonian cycle. In [8], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁,G₂,G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁G₂G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In [6], a characterization was given of all triples G₁,G₂,G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G₁,G₂,G₃ such that all G₁G₂G₃-free graphs are hamiltonian. In this paper we consider the question of which triples (including $K_{1,s}$, s ≥ 3) of forbidden subgraphs potentially imply all sufficiently large graphs are hamiltonian. For s ≥ 4 we characterize these families.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Forbidden triples implying Hamiltonicity: for all graphs

81%
Faudree R., Gould R., Jacobson M.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 1
47-54
EN
In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with $G_i = K_{1,3}$ for some i = 1, 2, or 3, such that all G₁G₂G₃-free graphs contain a hamiltonian cycle. In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁, G₂, G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁, G₂, G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G₁, G₂, G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G₁, G₂, G₃ such that all G₁G₂G₃-free graphs are hamiltonian.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Chvátal-Erdös type theorems

71%
Faudree J., Faudree R., Gould R., Jacobson M., Magnant C.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 2
245-256
EN
The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-k)/(k+1), and δ(G) ≥ α(G)+k-2, then G is hamiltonian. It is shown that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ 4k²+1, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected. This result supports the conjecture that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected, and the conjecture is verified for k = 3 and 4.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Linear forests and ordered cycles

62%
Chen G., Faudree R., Gould R., Jacobson M., Lesniak L., Pfender F.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
359-372
EN
A collection $L = P¹ ∪ P² ∪ ... ∪ P^t$ (1 ≤ t ≤ k) of t disjoint paths, s of them being singletons with |V(L)| = k is called a (k,t,s)-linear forest. A graph G is (k,t,s)-ordered if for every (k,t,s)-linear forest L in G there exists a cycle C in G that contains the paths of L in the designated order as subpaths. If the cycle is also a hamiltonian cycle, then G is said to be (k,t,s)-ordered hamiltonian. We give sharp sum of degree conditions for nonadjacent vertices that imply a graph is (k,t,s)-ordered hamiltonian.
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ć.