Partitionability of trees
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.
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.
The reaping number of a Boolean algebra is defined as the minimum size of a subset such that for each -partition of unity, some member of meets less than elements of . We show that for each , as conjectured by Dow, Steprāns and Watson. The proof relies on a partition theorem for finite trees; namely that every -branching tree whose maximal nodes are coloured with colours contains an -branching subtree using at most colours if and only if .
Minimum disconnecting cuts of connected graphs provide fundamental information about the connectivity structure of the graph. Spectral methods are well-known as stable and efficient means of finding good solutions to the balanced minimum cut problem. In this paper we generalise the standard balanced bisection problem for static graphs to a new “dynamic balanced bisection problem”, in which the bisecting cut should be minimal when the vertex-labelled graph is subjected to a general sequence of vertex...
A linear forest is a forest in which every component is a path. It is known that the set of vertices V(G) of any outerplanar graph G can be partitioned into two disjoint subsets V₁,V₂ such that induced subgraphs ⟨V₁⟩ and ⟨V₂⟩ are linear forests (we say G has an (LF, LF)-partition). In this paper, we present an extension of the above result to the class of planar graphs with a given number of internal vertices (i.e., vertices that do not belong to the external face at a certain fixed embedding of...
For a set S of connected graphs, a spanning subgraph F of a graph is called an S-factor if every component of F is isomorphic to a member of S. It was recently shown that every 2-connected cubic graph has a {Cₙ | n ≥ 4}-factor and a {Pₙ | n ≥ 6}-factor, where Cₙ and Pₙ denote the cycle and the path of order n, respectively (Kawarabayashi et al., J. Graph Theory, Vol. 39 (2002) 188-193). In this paper, we show that every connected cubic bipartite graph has a {Cₙ | n ≥ 6}-factor, and has a {Pₙ | n...
A path-neighborhood graph is a connected graph in which every neighborhood induces a path. In the main results the 3-sun-free path-neighborhood graphs are characterized. The 3-sun is obtained from a 6-cycle by adding three chords between the three pairs of vertices at distance 2. A Pk-graph is a path-neighborhood graph in which every neighborhood is a Pk, where Pk is the path on k vertices. The Pk-graphs are characterized for k ≤ 4.