Indexed by:
Abstract:
Let be a directed graph. A transitive fraternal augmentation of (G) over bar is a directed graph (H) over bar with the same vertex set, including all the arcs of (G) over bar and such that for any vertices x, y, z. 1. if (x, y) is an element of E((G) over bar) and (x, z) is an element of E((G) over bar) then (y, z) is an element of E((H) over bar) or (z, y) is an element of E((H) over bar) (fraternity); 2. if (x, y) is an element of E((G) over bar) and (y, z) is an element of E((G) over bar) then (x, z) is an element of E((H) over bar) (transitivity). In this paper, we explore some generalization of the transitive fraternal augmentations for directed graphs and its applications. In particular, we show that the 2-coloring number col(2)(G) <= 0(del(1)(G)del(0)(G)(2)), where del(k)(G) (k >= 0) denotes the greatest reduced average density with depth k of a graph G; we give a constructive proof that del(k)(G) bounds the distance (k + 1)-coloring number Col(k+1) (G) with a function f(del(k)(G)). On the other hand, del(k)(G) <= (col(2k+1) (G))(2k+1). We also show that an inductive generalization of transitive fraternal augmentations can be used to study nonrepetitive colorings of graphs. (C) 2009 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
DISCRETE MATHEMATICS
ISSN: 0012-365X
Year: 2009
Issue: 13
Volume: 309
Page: 4614-4623
0 . 5 4 8
JCR@2009
0 . 7 0 0
JCR@2023
ESI Discipline: MATHEMATICS;
JCR Journal Grade:3
CAS Journal Grade:1
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: