On normal partitions in cubic graphs

Jean-Luc Fouquet; Jean-Marie Vanherpe

Displaying similar documents to “On normal partitions in cubic graphs”

Finding $H$ -partitions efficiently

Simone Dantas, Celina M. H. de Figueiredo, Sylvain Gravier, Sulamita Klein (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We study the concept of an $H$ -partition of the vertex set of a graph $G$ , which includes all vertex partitioning problems into four parts which we require to be nonempty with only external constraints according to the structure of a model graph $H$ , with the exception of two cases, one that has already been classified as polynomial, and the other one remains unclassified. In the context of more general vertex-partition problems, the problems addressed in this paper have these properties:...

Cubic Graphs with Total Domatic Number at Least Two

Saieed Akbari, Mohammad Motiei, Sahand Mozaffari, Sina Yazdanbod (2018)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph with no isolated vertex. A total dominating set of G is a set S of vertices of G such that every vertex is adjacent to at least one vertex in S. The total domatic number of a graph is the maximum number of total dominating sets which partition the vertex set of G. In this paper we provide a criterion under which a cubic graph has total domatic number at least two.