Transactions on Combinatorics
Volume:4 Issue: 4, Dec 2015

Let p be a prime number and n be a positive integer. The graph Gp(n) is a graph with vertex set [n]=1,2,ldots,n , in which there is an arc from u to v if and only if uneqv and pnmidu . In this paper it is shown that Gp(n) is a perfect graph. In addition, an explicit formula for the chromatic number of such graph is given.

ýThe harmonic index of a connected graph Gý, ýdenoted by H(G)ý, ýisý ýdefined as H(G)=∑uv∈E(G)2du ý ýwhere dv is the degree of a vertex v in Gý. ýIn this paperý, ýexpressions for the Harary indices of theý ýjoiný, ýcorona productý, ýCartesian productý, ýcomposition and symmetric difference of graphs areý ýderivedý.

We consider a dynamic domination problem for graphs in which an infinite sequence of attacks occur at vertices with guards and the guard at the attacked vertex is required to vacate the vertex by moving to a neighboring vertex with no guard. Other guards are allowed to move at the same time, and before and after each attack and the resulting guard movements, the vertices containing guards form a dominating set of the graph. The minimum number of guards that can successfully defend the graph against such an arbitrary sequence of attacks is the m-eviction number. This parameter lies between the domination and independence numbers of the graph. We characterize the classes of trees for which the m-eviction number equals the domination number and the independence number, respectively.

The k-th semi total point graph Rk(G) of a graph G , is a graph obtained from G by adding k vertices corresponding to each edge and connecting them to endpoint of edge considered. In this paper, we obtain formulae for the resistance distance and Kirchhoff index of R Rk(G).

The bi-Cayley graph of a finite group G with respect to a subset S⊆G ý, ýwhich is denoted by \BCay(G,S) \ý, ýis the graph withý ývertex set G×{1,2 and edge set {{(x,1)ý,ý(sx,2)}∣x∈Gý,ý s∈S} ý. ýAý ýfinite group G is called a \textit{bi-Cayley integral group} if for any subset S ofýýGý,\BCay(G,S) is a graph with integer eigenvaluesý. ýIn this paper we proveý ýthat a finite group G is a bi-Cayley integral group if and only if G is isomorphic toý ýone of the groups Z2ký, ýfor someký, ý Z3 or S3ý.