Displaying similar documents to “Decomposition of complete graphs into factors of diameter two”

5-Stars of Low Weight in Normal Plane Maps with Minimum Degree 5

Oleg V. Borodin, Anna O. Ivanova, Tommy R. Jensen (2014)

Discussiones Mathematicae Graph Theory

Similarity:

It is known that there are normal plane maps M5 with minimum degree 5 such that the minimum degree-sum w(S5) of 5-stars at 5-vertices is arbitrarily large. In 1940, Lebesgue showed that if an M5 has no 4-stars of cyclic type (5, 6, 6, 5) centered at 5-vertices, then w(S5) ≤ 68. We improve this bound of 68 to 55 and give a construction of a (5, 6, 6, 5)-free M5 with w(S5) = 48

Total vertex irregularity strength of disjoint union of Helm graphs

Ali Ahmad, E.T. Baskoro, M. Imran (2012)

Discussiones Mathematicae Graph Theory

Similarity:

A total vertex irregular k-labeling φ of a graph G is a labeling of the vertices and edges of G with labels from the set {1,2,...,k} in such a way that for any two different vertices x and y their weights wt(x) and wt(y) are distinct. Here, the weight of a vertex x in G is the sum of the label of x and the labels of all edges incident with the vertex x. The minimum k for which the graph G has a vertex irregular total k-labeling is called the total vertex irregularity strength of G. We...

Edge Dominating Sets and Vertex Covers

Ronald Dutton, William F. Klostermeyer (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering, edge domination, and matching parameters is explored. In addition, the total vertex cover number is compared to the total domination number of trees and grid graphs.