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

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

Graphs with disjoint dominating and paired-dominating sets

100%
Southey J., Henning M.
Open Mathematics
|
2010
|
tom 8
|
nr 3
459-467
EN
A dominating set of a graph is a set of vertices such that every vertex not in the set is adjacent to a vertex in the set, while a paired-dominating set of a graph is a dominating set such that the subgraph induced by the dominating set contains a perfect matching. In this paper, we show that no minimum degree is sufficient to guarantee the existence of a disjoint dominating set and a paired-dominating set. However, we prove that the vertex set of every cubic graph can be partitioned into a dominating set and a paired-dominating set.
2
Content available remote

Hypergraphs with large transversal number and with edge sizes at least four

100%
Henning M., Löwenstein C.
Open Mathematics
|
2012
|
tom 10
|
nr 3
1133-1140
EN
Let H be a hypergraph on n vertices and m edges with all edges of size at least four. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge. Lai and Chang [An upper bound for the transversal numbers of 4-uniform hypergraphs, J. Combin. Theory Ser. B, 1990, 50(1), 129–133] proved that τ(H) ≤ 2(n+m)/9, while Chvátal and McDiarmid [Small transversals in hypergraphs, Combinatorica, 1992, 12(1), 19–26] proved that τ(H) ≤ (n + 2m)/6. In this paper, we characterize the connected hypergraphs that achieve equality in the Lai-Chang bound and in the Chvátal-McDiarmid bound.
3
Content available remote

A characterization of diameter-2-critical graphs with no antihole of length four

100%
Haynes T., Henning M.
Open Mathematics
|
2012
|
tom 10
|
nr 3
1125-1132
EN
A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence of our characterization, we prove the Murty-Simon Conjecture for graphs with no antihole of length four.
4
Content available remote

Dominating and total dominating partitions in cubic graphs

100%
Southey J., Henning M.
Open Mathematics
|
2011
|
tom 9
|
nr 3
699-708
EN
In this paper, we continue the study of domination and total domination in cubic graphs. It is known [Henning M.A., Southey J., A note on graphs with disjoint dominating and total dominating sets, Ars Combin., 2008, 89, 159–162] that every cubic graph has a dominating set and a total dominating set which are disjoint. In this paper we show that every connected cubic graph on nvertices has a total dominating set whose complement contains a dominating set such that the cardinality of the total dominating set is at most (n+2)/2, and this bound is essentially best possible.
5
Content available remote

A maximum degree theorem for diameter-2-critical graphs

81%
Haynes T., Henning M., Merwe L., Yeo A.
Open Mathematics
|
2014
|
tom 12
|
nr 12
1882-1889
EN
A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n 0 where n 0 is a tower of 2’s of height about 1014. The conjecture has yet to be proven for other values of n. Let Δ denote the maximum degree of G. We prove the following maximum degree theorems for diameter-2-critical graphs. If Δ ≥ 0.7 n, then the Murty-Simon Conjecture is true. If n ≥ 2000 and Δ ≥ 0.6789 n, then the Murty-Simon Conjecture is true.
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ć.