Transactions on Combinatorics
Volume:3 Issue: 2, Jun 2014

Let $A$ be a non-trivial abelian group and $A^{*}=Asetminus {0}$. A graph $G$ is said to be $A$-magic graph if there exists a labeling $l:E(G)rightarrow A^{*}$ such that the induced vertex labeling $l^{+}:V(G)rightarrow A$, define by $$l^+(v)=sum_{uvin E(G)} l(uv)$$ is a constant map.The set of all constant integers such that $sum_{uin N(v)} l(uv)=c$, for each $vin N(v)$, where $N(v)$ denotes the set of adjacent vertices to vertex $v$ in $G$, is called the index set of $G$ and denoted by ${rm In}_{A}(G).$ In this paper we determine the index set of certain planar graphs for $mathbb{Z}_{h}$, where $hin mathbb{N}$, such as wheels and fans.

Let $G$ be an $(n,m)$-graph. We say that $G$ has property $(ast)$ if for every pair of its adjacent vertices $x$ and $y$, there exists a vertex $z$, such that $z$ is not adjacent to either $x$ or $y$. If the graph $G$ has property $(ast)$, then its complement $overline G$ is connected, has diameter 2, and its Wiener index is equal to $binom{n}{2}+m$, i.e., the Wiener index is insensitive of any other structural details of the graph $G$. We characterize numerous classes of graphs possessing property $(ast)$, among which are trees, regular, and unicyclic graphs.

Let $n$ be any positive integer, the friendship graph $F_n$ consists of $n$ edge-disjoint triangles that all of them meeting in one vertex. A graph $G$ is called cospectral with a graph $H$ if their adjacency matrices have the same eigenvalues. Recently in href{http://arxiv.org/pdf/1310.6529v1.pdf}{http://arxiv.org/pdf/1310.6529v1.pdf} it is proved that if $G$ is any graph cospectral with $F_n$ ($nneq 16$), then $Gcong F_n$. In this note, we give a proof of a special case of the latter: Any connected graph cospectral with $F_n$ is isomorphic to $F_n$.Our proof is independent of ones given in href{http://arxiv.org/pdf/1310.6529v1.pdf http://arxiv.org/pdf/1310.6529v1.pdf} and the proofs are based on our recent results iven in [{em Trans. Comb.}, {bf 2} no. 4 (2013) 37-52.] using an upper bound for the argest eigenvalue of a connected graph given in {em J. Combinatorial Theory Ser. B} {bf 81} (2001) 177-183.].

Let $G$ be a connected graph. The multiplicative Zagreb eccentricity indices of $G$ are defined respectively as ${bf Pi}_1^*(G)=prod_{vin V(G)}varepsilon_G^2(v)$ and ${bf Pi}_2^*(G)=prod_{uvin E(G)}varepsilon_G(u)varepsilon_G(v)$, where $varepsilon_G(v)$ is the eccentricity of vertex $v$ in graph $G$ and $varepsilon_G^2(v)=(varepsilon_G(v))^2$. In this paper, we present some bounds of the multiplicative Zagreb eccentricity indices of Cartesian product graphs by means of some invariants of the factors and supply some exact expressions of ${bf Pi}_1^*$ and ${bf Pi}_2^*$ of some composite graphs, such as the join, disjunction, symmetric difference and composition of graphs, respectively.

For a given hypergraph $H$ with chromatic number $chi(H)$ and with no edge containing only one vertex, it is shown that the minimum number $l$ for which there exists a partition (also a covering) ${E_1,E_2,ldots,E_l}$ for $E(H)$, such that the hypergraph induced by $E_i$ for each $1leq ileq l$ is $k$-colorable, is $lceil log_{k} chi(H) rceil$.

A function $f:V(G)rightarrow {-1,0,1}$ is a {em minus dominating function} if for every vertex $vin V(G)$, $sum_{uin N[v]}f(u)ge 1$. A minus dominating function $f$ of $G$ is called a {em global minus dominating function} if $f$ is also a minus dominating function of the complement $overline{G}$ of $G$. The {em global minus domination number} $gamma_{g}^-(G)$ of $G$ is defined as $gamma_{g}^-(G)=min{sum_{vin V(G)} f(v)mid f mbox{is a global minus dominating function of} G}$. In this paper we initiate the study of global minus domination number in graphs and we establish lower and upper bounds for the global minus domination number.

A kernel J of a digraph D is an independent set of vertices of D such that for every vertex w ∈ V (D) ∖ J there exists an arc from w to a vertex in J. In this paper, among other results, a characterization of 2 -regular circulant digraph having a kernel is obtained. This characterization is a partial solution to the following problem: Characterize circulant digraphs which have kernels; it appeared in the book Digraphs - theory, algorithms and applications, Second Edition, Springer-Verlag, 2009, by J. Bang-Jensen and G. Gutin.

Given a graph $G = (V,E)$, a dominating set $D subseteq V$ is called a semi-strongsplit dominating set of $G$ if $|V setminus D| geq 1$ and the maximum degree of the subgraph induced by $V setminus D$ is 1. The minimum cardinality of a semi-strong split dominating set (SSSDS) of G is the semi-strong split domination number of G, denoted $gamma_{sss}(G)$. In this work, we introduce the concept and prove several results regarding it.