ON EQUITABLE VERTEX DISTINGUISHING EDGE COLORINGS OF TREES

It has been known that determining the exact value of vertex distinguishing edge index X ＇8（G） of a graph G is difficult, even for simple classes of graphs such as paths, cycles, bipartite complete graphs, complete, graphs, and graphs with maximum degree 2. Let rid（G） denote the number of vertices of degree d in G, and let X＇es（G） be the equitable vertex distinguishing edge index of G. We show that a tree T holds nl （T） ≤ X ＇s （T） ≤ n1 （T） ＋ 1 and X＇s（T） = X＇es（T） if T satisfies one of the following conditions （i） n2（T） ≤△（T） or （ii） there exists a constant c with respect to 0 〈 c 〈 1 such that n2（T） △ cn1（T） and ∑3 ≤d≤△（T）nd（T） ≤ （1 - c）n1（T） ＋ 1.

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph C is denoted by Xs＇8（G）. In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with △（G） ≥ 4, respectively.

GRAPH COLORING BASED CHANNEL ASSIGNMENT FRAMEWORK FOR RURAL WIRELESS MESH NETWORKS

IEEE 802.11 based wireless mesh networks with directional antennas are expected to be a new promising technology and an economic approach for providing wireless broadband services in rural areas.In this paper,we discuss interference models and address how they can affect the design of channel assignment in rural mesh networks.We present a new channel assignment framework based on graph coloring for rural wireless mesh networks.The goal of the framework is to allow synchronously transmitting or receiving data from multiple neighbor links at the same time,and continuously doing full-duplex data transfer on every link,creating an efficient rural mesh network without interference.Channel assignment is shown to be NP-hard.We frame this channel allocation problem in terms of Adjacent Vertex Distinguishing Edge Coloring(AVDEC).Detailed assignment results on grid topology are presented and discussed.Furthermore,we design an algorithm.Finally,we evaluate the performance of the proposed algorithm through extensive simulations and show the algorithm is effective to the regular grid topologies,and the number of colors used by the algorithm is upper bounded by+1.Hence the algorithm guarantees that the number of channels available in standards such as IEEE802.11a is sufficient to have a valid AVDEC for many grid topologies.We also evaluate the proposed algorithm for arbitrary graphs.The algorithm provides a lower upper bound on the minimum number of channels to the AVDEC index channel assignment problem.

An Upper Bound for the Adjacent Vertex Distinguishing Acyclic Edge Chromatic Number of a Graph

A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to v, where uv ∈E（G）. The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ＇αα（G）, is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G（V, E） is a graph with no isolated edges, then χ＇αα（G）≤32△.