Transactions on Combinatorics
Volume:4 Issue: 1, Mar 2015

A Roman dominating function (RDF) on a graph G = (V,E) is defined to be a function satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. A set S V is a Restrained dominating set if every vertex not in S is adjacent to a vertex in S and to a vertex in. We define a Restrained Roman dominating function on a graph G = (V,E) to be a function satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2 and at least one vertex w for which f(w) = 0. The weight of a Restrained Roman dominating function is the value. The minimum weight of a Restrained Roman dominating function on a graph G is called the Restrained Roman domination number of G and denoted by. In this paper, we initiate a study of this parameter.

For a graph G, let D(G) be the set of all strong orientations of G. The orientationnumber of G is min {d(D) |D belongs to D(G)}, where d(D) denotes the diameterof the digraph D. In this paper, we determine the orientation number for some subgraphs of complete bipartite graphs.

Let $f$ be a proper $k$-coloring of a connected graph $G$ and $Pi=(V_1,V_2,ldots,V_k)$ be an ordered partition of $V(G)$ into the resulting color classes. For a vertex $v$ of $G$, the color code of $v$ with respect to $Pi$ is defined to be the ordered $k$-tuple $c_{{}_Pi}(v)=(d(v,V_1),d(v,V_2),ldots,d(v,V_k)),$ where $d(v,V_i)=min{d(v,x):~xin V_i}, 1leq ileq k$. If distinct vertices have distinct color codes, then $f$ is called a locating coloring. The minimum number of colors needed in a locating coloring of $G$ is the locating chromatic number of $G$, denoted by $Cchi_{{}_L}(G)$. In this paper, we study the locating chromatic numbers of trees. We provide a counter example to a theorem of Gary Chartrand et al. [G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, P. Zhang, The locating-chromatic number of a graph, Bull. Inst. Combin. Appl. 36 (2002) 89-101] about the locating chromatic numbers of trees. Also, we offer a new bound for the locating chromatic number of trees. Then, by constructing a special family of trees, we show that this bound is best possible.

The first Zagreb index $M_1$ of a graph $G$ is equal to the sum of squares of degrees of the vertices of $G$. Goubko proved that for trees with $n_1$ pendent vertices, $M_1 geq 9,n_1-16$. We show how this result can be extended to hold for any connected graph with cyclomatic number $gamma geq 0$. In addition, graphs with $n$ vertices, $n_1$ pendent vertices, cyclomatic number $gamma$, and minimal $M_1$ are characterized. Explicit expressions for minimal $M_1$ are given for $gamma=0,1,2$, which directly can be extended for $gamma>2$.

‎A $(p‎,‎q)$ graph $G$ is said to have a $k$-odd mean‎ ‎labeling $(k ge 1)$ if there exists an injection $f‎: ‎V‎ ‎to {0‎, ‎1‎, ‎2‎, ‎ldots‎, ‎2k‎ + ‎2q‎ - ‎3}$ such that the‎ ‎induced map $f^*$ defined on $E$ by $f^*(uv) =‎ ‎leftlceil frac{f(u)+f(v)}{2}rightrceil$ is a‎ ‎bijection from $E$ to ${2k - ‎‎‎1‎, ‎2k‎ + ‎1‎, ‎2k‎ + ‎3‎, ‎ldots‎, ‎2‎ ‎k‎ + ‎2q‎ - ‎3}$‎. ‎A graph that admits $k$-odd mean‎ ‎labeling is called $k$-odd mean graph‎. ‎In this paper‎, ‎we investigate $k$-odd mean labeling of prism $C_m times‎ ‎P_n$‎.

The skew energy of oriented graphs is de ned as the sum of the norms of all the eigenvalues of the skew adjacency matrix. In this note, we obtain some upper bounds for the skew energy of any oriented graphs, which improve the known upper bound obtained by Adiga et al.