Neighborhood Pseudo Chromatic Polynomial of Graphs

摘要

In a graphical representation of computer network G(V,E), processors are represented by vertices v ∈ V and direct communication links between pairs of processors are represented by edges e ∈ E. A processor can communicate with its direct neighbors if they have a common information protocol. But otherwise, each processor also has a translator that can be used to convert the protocol. One of the problem is to find the number of ways of using the translators in the network with each processor has at least one neighbor receives the common information, subject to the restriction that each processor should be able to communicate with all of its neighbors. This network problem can be analysed using neighborhood pseudo chromatic polynomial. Neighborhood pseudo chromatic number of a graph G, denoted by ψ_(nhd)(G), is the maximum number of colors used in a pseudo coloring of G such that every vertex has at least two vertices in its closed neighborhood receiving the same color. Neighborhood pseudo chromatic polynomial is a polynomial of a graph G which counts the number of distinct ways to neighborhood pseudo color G with not more than a given number of colors. In this paper, we find the neighborhood pseudo chromatic polynomial of some standard graphs.