Transactions on Combinatorics
Volume:3 Issue: 4, Dec 2014

Let $G$ be a simple graph with vertex set $V(G) = {v_1, v_2,ldots, v_n}$ and edge set $E(G) = {e_1, e_2,ldots, e_m}$. Similar to the Randi''c matrix, here we introduce the Randi''c incidence matrix of a graph $G$, denoted by $I_R(G)$, which is defined as the $ntimes m$ matrix whose $(i, j)$-entry is $(d_i)^{-frac{1}{2}}$ if $v_i$ is incident to $e_j$ and $0$ otherwise. Naturally, the Randi''c incidence energy $I_RE$ of $G$ is the sum of the singular values of $I_R(G)$. We establish lower and upper bounds for the Randi''c incidence energy. Graphs for which these bounds are best possible are characterized. Moreover, we investigate the relation between the Randi''c incidence energy of a graph and that of its subgraphs. Also we give a sharp upper bound for the Randi''c incidence energy of a bipartite graph and determine the trees with the maximum Randi''c incidence energy among all $n$-vertex trees. As a result, some results are very different from those for incidence energy.

A signed graph (marked graph) is an ordered pair $S=(G,sigma)$ $(S=(G,mu))$, where $G=(V,E)$ is a graph called the underlying graph of $S$ and $sigma:Erightarrow{+,-}$ $(mu:Vrightarrow{+,-})$ is a function. For a graph $G$, $V(G), E(G)$ and $C(G)$ denote its vertex set, edge set and cut-vertex set, respectively. The lict graph $L_{c}(G)$ of a graph $G=(V,E)$ is defined as the graph having vertex set $E(G)cup C(G)$ in which two vertices are adjacent if and only if they correspond to adjacent edges of $G$ or one corresponds to an edge $e_{i}$ of $G$ and the other corresponds to a cut-vertex $c_{j}$ of $G$ such that $e_{i}$ is incident with $c_{j}$. In this paper, we introduce lict sigraphs, as a natural extension of the notion of lict graph to the realm of signed graphs. We show that every lict sigraph is balanced. We characterize signed graphs $S$ and $S^{''}$ for which $Ssim L_{c}(S)$, $eta(S)sim L_{c}(S)$, $L(S)sim L_{c}(S'')$, $J(S)sim L_{c}(S^{''})$ and $T_{1}(S)sim L_{c}(S^{''})$, where $eta(S)$, $L(S)$, $J(S)$ and $T_{1}(S)$ are negation, line graph, jump graph and semitotal line sigraph of $S$, respectively, and $sim$ means switching equivalence.

A subset S of vertices in a graph G is called a geodetic set if every vertex not inS lies on a shortest path between two vertices from S. A subset D of vertices in G iscalled dominating set if every vertex not in D has at least one neighbor in D. A geodeticdominating set S is both a geodetic and a dominating set. The geodetic (domination,geodetic domination) number g(G)(γ(G),γ_g(G)) of G is the minimum cardinality amongall geodetic (dominating, geodetic dominating) sets in G. In this paper, we show that ifa triangle free graph G has minimum degree at least 2 and g(G) = 2, then γ_g(G) = γ(G).It is shown, for every nontrivial connected graph G with γ(G) = 2 and diam(G) > 3,that γ_g(G) > g(G). The lower bound for the geodetic domination number of Cartesianproduct graphs is proved. Geodetic domination number of product of cycles (paths)are determined. In this work, we also determine some bounds and exact values of thegeodetic domination number of strong product of graphs.

The second multiplicative Zagreb coindex of a simple graph G is defined as: bar {{Pi}}_2 (G) =prod_{uv notin E (G)}{d_G (u) d_G (v)} where d_G (u) denotes the degree of the vertex u of G. In this paper، we compare bar {{Pi}}_2-index with some well-known graph invariants such as the Wiener index، Schultz index، eccentric connectivity index، total eccentricity، eccentric-distance sum، the first Zagreb index and coindex and the first multiplicative Zagreb index and coindex.

In this work، using eigenvalues and eigenvectors of unitary Cayley graphs over finite local rings and elementary linear algebra، we characterize which local rings allowing PST occurring in its unitary Cayley graph. Moreover، we have some developments when $R$ is a product of local rings.

Let dn;m = 2n+1 and En;m be the graph obtained from a path Pdn;m+1 = v0v1:::vdn;m by joining each vertex of Kn by joining each vertex of Kn. Zhang, Liu and Zhou [On the maximal eccentric connectivity indices of graphs, Appl. Math. J. Chinese Univ., in press] conjectured that if dn;m > 3, then En;m is the graph with maximal eccentric connectivity ndex among all connected graph with n vertices and m edges. In this note, we prove this conjecture. Moreover, we present the graph with maximal eccentric connectivity index among the connected graphs with n vertices. Finally, the minimum of this graph invariant n the classes of tricyclic and tetracyclic graphs are computed.