Displaying similar documents to “On the Zagreb index of quasi-tree graphs.”

On Graphs with Disjoint Dominating and 2-Dominating Sets

Michael A. Henning, Douglas F. Rall (2013)

Discussiones Mathematicae Graph Theory

Similarity:

A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D ∪ D2 necessarily contains all vertices...

On Unique Minimum Dominating Sets in Some Cartesian Product Graphs

Jason T. Hedetniemi (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Unique minimum vertex dominating sets in the Cartesian product of a graph with a complete graph are considered. We first give properties of such sets when they exist. We then show that when the first factor of the product is a tree, consideration of the tree alone is sufficient to determine if the product has a unique minimum dominating set.

On the Relationships between Zero Forcing Numbers and Certain Graph Coverings

Fatemeh Alinaghipour Taklimi, Shaun Fallat, Karen Meagher (2014)

Special Matrices

Similarity:

The zero forcing number and the positive zero forcing number of a graph are two graph parameters that arise from two types of graph colourings. The zero forcing number is an upper bound on the minimum number of induced paths in the graph that cover all the vertices of the graph, while the positive zero forcing number is an upper bound on the minimum number of induced trees in the graph needed to cover all the vertices in the graph. We show that for a block-cycle graph the zero forcing...

Tree-Like Partial Hamming Graphs

Tanja Gologranc (2014)

Discussiones Mathematicae Graph Theory

Similarity:

Tree-like partial cubes were introduced in [B. Brešar, W. Imrich, S. Klavžar, Tree-like isometric subgraphs of hypercubes, Discuss. Math. Graph Theory, 23 (2003), 227-240] as a generalization of median graphs. We present some incorrectnesses from that article. In particular we point to a gap in the proof of the theorem about the dismantlability of the cube graph of a tree-like partial cube and give a new proof of that result, which holds also for a bigger class of graphs, so called tree-like...