EuDML | Browse

A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.

Partitioning a planar graph without chordal 5-cycles into two forests

Yang Wang, Weifan Wang, Jiangxu Kong, Yiqiao Wang (2024)

Czechoslovak Mathematical Journal

It was known that the vertex set of every planar graph can be partitioned into three forests. We prove that the vertex set of a planar graph without chordal 5-cycles can be partitioned into two forests. This extends a result obtained by Raspaud and Wang in 2008.

Partitioning planar graph of girth 5 into two forests with maximum degree 4

Min Chen, André Raspaud, Weifan Wang, Weiqiang Yu (2024)

Czechoslovak Mathematical Journal

Given a graph $G = (V, E)$ , if we can partition the vertex set $V$ into two nonempty subsets $V_{1}$ and $V_{2}$ which satisfy $Δ (G [V_{1}]) \leq d_{1}$ and $Δ (G [V_{2}]) \leq d_{2}$ , then we say $G$ has a $(Δ_{d_{1}}, Δ_{d_{2}})$ -partition. And we say $G$ admits an $(F_{d_{1}}, F_{d_{2}})$ -partition if $G [V_{1}]$ and $G [V_{2}]$ are both forests whose maximum degree is at most $d_{1}$ and $d_{2}$ , respectively. We show that every planar graph with girth at least 5 has an $(F_{4}, F_{4})$ -partition.

Partitions and congruences in algebras. I. Basic properties

Tran Duc Mai (1974)

Archivum Mathematicum

Partitions and edge colourings of multigraphs.

Kostochka, Alexandr V., Stiebitz, Michael (2008)

The Electronic Journal of Combinatorics [electronic only]

Partitions excluding specific polygonal numbers as parts.

Sellers, James A. (2004)

Journal of Integer Sequences [electronic only]

Partitions of a graph into cycles containing a specified linear forest

Ryota Matsubara, Hajime Matsumura (2008)

Discussiones Mathematicae Graph Theory

In this note, we consider the partition of a graph into cycles containing a specified linear forest. Minimum degree and degree sum conditions are given, which are best possible.

Partitions of Graphs into Coverings and Hypergraphs into Transversals

D. de Werra (1974)

Commentarii mathematici Helvetici

Partitions of $k$ -branching trees and the reaping number of Boolean algebras

Claude Laflamme (1993)

Commentationes Mathematicae Universitatis Carolinae

The reaping number $𝔯_{m, n} (𝔹)$ of a Boolean algebra $𝔹$ is defined as the minimum size of a subset $𝒜 \subseteq 𝔹 ∖ {𝐎}$ such that for each $m$ -partition $𝒫$ of unity, some member of $𝒜$ meets less than $n$ elements of $𝒫$ . We show that for each $𝔹$ , $𝔯_{m, n} (𝔹) = 𝔯_{⌈ \frac{m}{n - 1} ⌉, 2} (𝔹)$ as conjectured by Dow, Steprāns and Watson. The proof relies on a partition theorem for finite trees; namely that every $k$ -branching tree whose maximal nodes are coloured with $ℓ$ colours contains an $m$ -branching subtree using at most $n$ colours if and only if $⌈ \frac{ℓ}{n} ⌉ < ⌈ \frac{k}{m - 1} ⌉$ .

Currently displaying 81 – 100 of 376

Previous Page 5 Next