TRANSACTIONS ON COMBINATORICS
Year:2013 | Volume:2 | Issue:4|Papers Count:6

A Roman dominating function on a graph G= (V, E) is a function f: V®{0, 1, 2} satisfying the condition that every vertex v for which f (v) =0 is adjacent to at least one vertex u for which f (u) =2. The weight of a Roman dominating function is the value w (f) = S vÎV f (v). The Roman domination number of a graph G, denoted by yR (G), equals the minimum weight of a Roman dominating function on G. The Roman game domination subdivision number of a graph G is defined by the following game. Two players D and A, D playing first, alternately mark or subdivide an edge of G which is not yet marked nor subdivided. The game ends when all the edges of G are marked or subdivided and results in a new graph G’. The purpose of D is to minimize the Roman domination number yR (G’) of G’ while A tries to maximize it. If both A and D play according to their optimal strategies, R (G0) is well defined. We call this number the Roman game domination subdivision number of G and denote it by yRgs (G). In this paper we initiate the study of the Roman game domination subdivision number of a graph and present sharp bounds on the Roman game domination subdivision number of a tree.

The reciprocal degree distance (RDD), defined for a connected graph G as vertex-degree- weighted sum of the reciprocal distances, that is, RDD (G) = S u, vÎV (G) dG (u)+dG (v)/dG (u, v). The reciprocal degree distance is a weight version of the Harary index, just as the degree distance is a weight version of the Wiener index. In this paper, we present exact formulae for the reciprocal degree distance of join, tensor product, strong product and wreath product of graphs in terms of other graph invariants including the degree distance, Harary index, the first Zagreb index and first Zagreb coindex. Finally, we apply some of our results to compute the reciprocal degree distance of fan graph, wheel graph, open fence and closed fence graphs.

In this article a graph theoretical approach is employed to study some speci cations of dynamic systems with time delay in the inputs and states, such as structural controllability and observ- ability. First, the zero and non-zero parameters of a proposed system have been determined, next the general structure of the system is presented by a graph which is constructed by non-zero parameters.The structural controllability and observability of the system is investigated using the corresponding graph. Our results are expressed for multi-agents systems with dead-time. As an application we nd a minimum set of leaders to control a given multi-agent system.

Let n be any positive integer and Fn be the friendship (or Dutch windmill) graph with 2n+1 vertices and 3n edges. Here we study graphs with the same adjacency spectrum as Fn. Two graphs are called cospectral if the eigenvalues multiset of their adjacency matrices are the same. Let G be a graph cospectral with Fn. Here we prove that if G has no cycle of length 4 or 5, then G @ Fn. Moreover if G is connected and planar then G @ Fn. All but one of connected components of G are isomorphic to K2.The complement `Fn of the friendship graph is determined by its adjacency eigenvalues, that is, if `Fn is cospectral with a graph H, then H @`Fn.

Let G= (V, E) be a graph. By directional labeling (or d-labeling) of an edge x=uv of G by an ordered n-tuple (a1, a2,…, an), we mean a labeling of the edge x such that we consider the label on uv as (a1, a2, …, an) in the direction from u to v, and the label on x as (an, an-1,…, a1) in the direction from v to u. In this paper, we study graphs, called (n, d) -sigraphs, in which every edge is d-labeled by an n-tuple (a1, a2, …, an), where ak Î {+,-}, for 1 £k£ n. In this paper, we give dierent notion of balance: symmetric balance in a (n, d) -sigraph and obtain some characterizations.

Let G= (V, E) be a connected simple graph. A labeling f: V®Z2 induces an edge labeling f*: E®Z2 defined by f* (xy) =f (x)+f (y) for each xy Î E. For i Î Z2, let vf (i) =|f-1 (i)| and ef (i) =|f*-1 (i)|. A labeling f is called friendly if |vf (1) - vf (0)|£1. The full friendly index set of G consists all possible dierences between the number of edges labeled by 1 and the number of edges labeled by 0. In recent years, full friendly index sets for certain graphs were studied, such as tori, grids P2´Pn, and cylinders Cm´Pn for some n and m. In this paper we study the full friendly index sets of cylinder graphs Cm´P2 for m ³ 3, Cm´P3 for m ³4 and C3´Pn for n ³ 4. The results in this paper complement the existing results in literature, so the full friendly index set of cylinder graphs are completely determined.