Search

A subset S of vertices of a graph G with no isolated vertex is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex in V ( G) − S is also adjacent to a vertex in V ( G) − S. The total restrained domination number of G is the minimum cardinality of a total restrained dominating set of G. In this paper we initiate the study of total restrained bondage in graphs. The total restrained bondage number in a graph G with no isolated vertex, is the minimum cardinality of a subset of edges E such that G - E has no isolated vertex and the total restrained domination number of G - E is greater than the total restrained domination number of G. We obtain several properties, exact values and bounds for the total restrained bondage number of a graph. [ABSTRACT FROM AUTHOR]

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc( G) of the graph G is the smallest number of colors in a linear coloring of G. In this paper, it is proved that every planar graph G with girth g and maximum degree Δ has (1) lc( G) ≤ Δ + 21 if Δ ≥ 9; (2) $$lc(G) \leqslant \left\lceil {\tfrac{\Delta } {2}} \right\rceil + 7$$ if g ≥ 5; (3) $$lc(G) \leqslant \left\lceil {\tfrac{\Delta } {2}} \right\rceil + 2$$ if g ≥ 7 and Δ≥ 7. [ABSTRACT FROM AUTHOR]