فهرست مطالب

  • Volume:4 Issue:1, 2015
  • تاریخ انتشار: 1393/10/11
  • تعداد عناوین: 6
|
  • Roushini Leely Pushpam, Padmapriea Sampath Pages 1-17
    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.
    Keywords: Domination, Roman domination, Restrained domination
  • R. Lakshmi, G. Rajasekaran, R. Sampathkumar Pages 19-29
    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.
    Keywords: subgraphs of complete bipartite graphs, orientation, orientation number, $Z, 2^n$, partition, $Z, 2^n$, set
  • Ali Behtoei, Mahdi Anbarloei Pages 31-41
    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.
    Keywords: Locating coloring, Locating chromatic number, tree, Maximum degree
  • Ivan Gutman, Muhammad Kamran Jamil, Naveed Akhter Pages 43-48
    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$.
    Keywords: degree (of vertex), Zagreb index, first Zagreb index, extremal graphs
  • B. Gayathri, K. Amuthavalli Pages 49-56
    ‎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$‎.
    Keywords: k, odd mean labeling, k, odd mean graph, Prism
  • Jun He, Ting, Zhu Huang Pages 57-61
    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.
    Keywords: oriented graph, skew adjacency matrix, skew spectral radius, skew energy