Search

A graph $G$ is factored into graphs $H$ and $K$ via a matrix product if there exist adjacency matrices $A$, $B$, and $C$ of $G$, $H$, and $K$, respectively, such that $A = BC$. In this paper, we study the spectral aspects of the matrix product of graphs, including regularity, bipartiteness, and connectivity. We show that if a graph $G$ is factored into a connected graph $H$ and a graph $K$ with no isolated vertices, then certain properties hold. If $H$ is non-bipartite, then $G$ is connected. If $H$ is bipartite and $G$ is not connected, then $K$ is a regular bipartite graph, and consequently, $n$ is even. Furthermore, we show that trees are not factorizable, which answers a question posed by Maghsoudi et al., Comment: Comments are welcome

Let $G_S$ be the graph obtained by attaching a self-loop at every vertex in $S \subseteq V(G)$ of a simple graph $G$ of order $n.$ In this paper, we explore several new results related to the line graph $L(G_S)$ of $G_S.$ Particularly, we show that every eigenvalue of $L(G_S)$ must be at least $-2,$ and relate the characteristic polynomial of the line graph $L(G)$ of $G$ with the characteristic polynomial of the line graph $L(\widehat{G})$ of a self-loop graph $\widehat{G}$, which is obtained by attaching a self-loop at each vertex of $G$. Then, we provide some new bounds for the eigenvalues and energy of $G_S.$ As one of the consequences, we obtain that the energy of a connected regular complete multipartite graph is not greater than the energy of the corresponding self-loop graph. Lastly, we establish a lower bound of the spectral radius in terms of the first Zagreb index $M_1(G)$ and the minimum degree $\delta(G),$ as well as proving two Nordhaus-Gaddum-type bounds for the spectral radius and the energy of $G_S,$ respectively., Comment: 19 pages. To appear in Bulletin of the Malaysian Mathematical Sciences Society

The $\Delta$-edge stability number ${\rm es}_{\Delta}(G)$ of a graph $G$ is the minimum number of edges of $G$ whose removal results in a subgraph $H$ with $\Delta(H) = \Delta(G)-1$. Sets whose removal results in a subgraph with smaller maximum degree are called mitigating sets. It is proved that there always exists a mitigating set which induces a disjoint union of paths of order $2$ or $3$. Minimum mitigating sets which induce matchings are characterized. It is proved that to obtain an upper bound of the form ${\rm es}_{\Delta}(G) \leq c |V(G)|$ for an arbitrary graph $G$ of given maximum degree $\Delta$, where $c$ is a given constant, it suffices to prove the bound for $\Delta$-regular graphs. Sharp upper bounds of this form are derived for regular graphs. It is proved that if $\Delta(G) \geq\frac{|V(G)|-2}{3}$ or the induced subgraph on maximum degree vertices has a $\Delta(G)$-edge coloring, then ${\rm es}_{\Delta}(G) \le |V(G)|/2$.

We investigate how small the Randi\'c index of a graph can be in terms of its matching number, and prove several results. We give best-possible linear bounds for graphs of small excess and for subcubic graphs; in the former case the size of excess we permit is qualitatively the best possible. We show that a linear bound holds for any sparse hereditary graph class (such as planar graphs). In general, however, we show that it can be much smaller than linear. We determine the asymptotic growth rate of the minimum Randi\'c index for graphs with a near perfect matching, and conjecture that the same bounds hold for all graphs., Comment: 11 pages, 2 figures. Added the observation that the assumptions in Corollary 6 are necessary, and other minor remarks

Let $G_S$ be a graph with loops obtained from a graph $G$ of order $n$ and loops at $S \subseteq V(G)$. In this paper, we establish a neccesary and sufficient condition on the bipartititeness of a connected graph $G$ and the spectrum Spec($G_S$) and Spec($G_{V(G)\backslash S}$). We also prove that for every $S \subseteq V(G)$, $E(G_S) \geq E(G)$ when $G$ is bipartite. Moreover, we provide an identification of the spectrum of complete graphs $K_n$ and complete bipartite graphs $K_{m,n}$ with loops. We characterize any graphs with loops of order n whose eigenvalues are all positive or non-negative, and also any graphs with a few distinct eigenvalues. Finally, we provide some bounds related to $G_S$., Comment: 16 pages, published version

Let $G=(V,E)$ be a simple graph. A dominating set of $G$ is a subset $S\subseteq V$ such that every vertex not in $S$ is adjacent to at least one vertex in $S$. The cardinality of a smallest dominating set of $G$, denoted by $\gamma(G)$, is the domination number of $G$. Two vertices are neighbors if they are adjacent. A super dominating set is a dominating set $S$ with the additional property that every vertex in $V \setminus S$ has a neighbor in $S$ that is adjacent to no other vertex in $V \setminus S$. Moreover if every vertex in $V \setminus S$ has degree at least~$2$, then $S$ is an end super dominating set. The end super domination number is the minimum cardinality of an end super dominating set. We give applications of end super dominating sets as main servers and temporary servers of networks. We determine the exact value of the end super domination number for specific classes of graphs, and we count the number of end super dominating sets in these graphs. Tight upper bounds on the end super domination number are established, where the graph is modified by vertex (edge) removal and contraction., Comment: 25 pages, 11 figures

Let $G$ be a graph of order $n$ with adjacency matrix $A(G)$. The \textit{energy} of graph $G$, denoted by $\mathcal{E}(G)$, is defined as the sum of absolute value of eigenvalues of $A(G)$. It was conjectured that if $A(G)$ is non-singular, then $\mathcal{E}(G)\geq\Delta(G)+\delta(G)$. In this paper we propose a stronger conjecture as for $n \geq 5$, $\mathcal{E}(G)\geq n-1+ d$, where $d$ is the average degree of $G$. Here, we show that conjecture holds for bipartite graphs, planar graphs and for the graphs with $d \leq n-2\ln n -3$

The chromatic edge stability index $\mathrm{es}_{\chi'}(G)$ of a graph $G$ is the minimum number of edges whose removal results in a graph with smaller chromatic index. We give best-possible upper bounds on $\mathrm{es}_{\chi'}(G)$ in terms of the number of vertices of degree $\Delta(G)$ (if $G$ is Class 2), and the numbers of vertices of degree $\Delta(G)$ and ${\Delta(G)-1}$ (if $G$ is Class 1). If $G$ is bipartite we give an exact expression for $\mathrm{es}_{\chi'}(G)$ involving the maximum size of a matching in the subgraph induced by vertices of degree $\Delta(G)$. Finally, we consider whether a minimum mitigating set, that is a set of size $\mathrm{es}_{\chi'}(G)$ whose removal reduces the chromatic index, has the property that every edge meets a vertex of degree at least $\Delta(G)-1$; we prove that this is true for some minimum mitigating set of $G$, but not necessarily for every minimum mitigating set of $G$., Comment: 10 pages, 4 figures. Fina version, to appear in Discrete Mathematics

The chromatic vertex (resp.\ edge) stability number ${\rm vs}_{\chi}(G)$ (resp.\ ${\rm es}_{\chi}(G)$) of a graph $G$ is the minimum number of vertices (resp.\ edges) whose deletion results in a graph $H$ with $\chi(H)=\chi(G)-1$. In the main result it is proved that if $G$ is a graph with $\chi(G) \in \{ \Delta(G), \Delta(G)+1 \}$, then ${\rm vs}_{\chi}(G) = {\rm ivs}_{\chi}(G)$, where ${\rm ivs}_{\chi}(G)$ is the independent chromatic vertex stability number. The result need not hold for graphs $G$ with $\chi(G) \le \frac{\Delta(G)+1}{2}$. It is proved that if $\chi(G) > \frac{\Delta(G)}{2}+1$, then ${\rm vs}_{\chi}(G) = {\rm es}_{\chi}(G)$. A Nordhaus-Gaddum-type result on the chromatic vertex stability number is also given.

Given a non-trivial graph $G$, the minimum cardinality of a set of edges $F$ in $G$ such that $\chi'(G \setminus F)<\chi'(G)$ is called the chromatic edge stability index of $G$, denoted by $es_{\chi'}(G)$, and such a (smallest) set $F$ is called a (minimum) mitigating set. While $1\le es_{\chi'}(G)\le \lfloor n/2\rfloor$ holds for any graph $G$, we investigate the graphs with extremal and near-extremal values of $es_{\chi'}(G)$. The graphs $G$ with $es_{\chi'}(G)=\lfloor n/2\rfloor$ are classified, and the graphs $G$ with $es_{\chi'}(G)=\lfloor n/2\rfloor-1$ and $\chi'(G)=\Delta(G)+1$ are characterized. We establish that the odd cycles and $K_2$ are exactly the regular connected graphs with the chromatic edge stability index $1$; on the other hand, we prove that it is NP-hard to verify whether a graph $G$ has $es_{\chi'}(G)=1$. We also prove that every minimum mitigating set of an $r$-regular graph $G$, where $r\ne 4$, with $es_{\chi'}(G)=2$ is a matching. Furthermore, we propose a conjecture that for every graph $G$ there exists a minimum mitigating set, which is a matching, and prove that the conjecture holds for graphs $G$ with $es_{\chi'}(G)\in\{1,2,\lfloor n/2\rfloor-1,\lfloor n/2\rfloor\}$, and for bipartite graphs., Comment: 17 pages

A Deza graph $G$ with parameters $(n,k,b,a)$ is a $k$-regular graph with $n$ vertices such that any two distinct vertices have $b$ or $a$ common neighbours. The children $G_A$ and $G_B$ of a Deza graph $G$ are defined on the vertex set of $G$ such that every two distinct vertices are adjacent in $G_A$ or $G_B$ if and only if they have $a$ or $b$ common neighbours, respectively. A strongly Deza graph is a Deza graph with strongly regular children. In this paper we give a spectral characterisation of strongly Deza graphs, show relationships between eigenvalues, and study strongly Deza graphs which are distance-regular.

Given a $t$-$(v, k, \lambda)$ design, $\mathcal{D}=(X,\mathcal{B})$, a zero-sum $n$-flow of $\mathcal{D}$ is a map $f : \mathcal{B}\longrightarrow \{\pm1,\ldots, \pm(n-1)\}$ such that for any point $x\in X$, the sum of $f$ over all blocks incident with $x$ is zero. For a positive integer $k$, we find a zero-sum $k$-flow for an STS$(u w)$ and for an STS$(2v+7)$ for $v\equiv 1~(\mathrm{mod}~4)$, if there are STS$(u)$, STS$(w)$ and STS$(v)$ such that the STS$(u)$ and STS$(v)$ both have a zero-sum $k$-flow. In 2015, it was conjectured that for $v>7$ every STS$(v)$ admits a zero-sum $3$-flow. Here, it is shown that many cyclic STS$(v)$ have a zero-sum $3$-flow. Also, we investigate the existence of zero-sum flows for some Steiner quadruple systems.

In 2011, Haemers asked the following question: If $S$ is the Seidel matrix of a graph of order $n$ and $S$ is singular, does there exist an eigenvector of $S$ corresponding to $0$ which has only $\pm 1$ elements? In this paper, we construct infinite families of graphs which give a negative answer to this question. One of our constructions implies that for every natural number $N$, there exists a graph whose Seidel matrix $S$ is singular such that for any integer vector in the nullspace of $S$, the absolute value of any entry in this vector is more than $N$. We also derive some characteristics of vectors in the nullspace of Seidel matrices, which lead to some necessary conditions for the singularity of Seidel matrices. Finally, we obtain some properties of the graphs which affirm the above question.

Let $G$ be a graph, a dominating induced matching (DIM) of $G$ is an induced matching that dominates every edge of $G$. In this paper we show that if a graph $G$ has a DIM, then $\chi(G) \leqslant 3$. Also, it is shown that if $G$ is a connected graph whose all edges can be partitioned into DIM, then $G$ is either a regular graph or a biregular graph and indeed we characterize all graphs whose edge set can be partitioned into DIM. Also, we prove that if $G$ is an $r$-regular graph of order $n$ whose edges can be partitioned into DIM, then $n$ is divisible by $\binom{2r - 1}{r - 1}$ and $n = \binom{2r - 1}{r - 1}$ if and only if $G$ is the Kneser graph with parameters $r-1$, $2r-1$.

Let $G$ be a graph and $a(G)$, LIF$(G)$ denote the maximum orders of an induced forest and an induced linear forest of $G$, respectively. It is well-known that if $G$ is an $r$-regular graph of order $n$, then $a(G) \geq \frac{2}{r+1}n$. In this paper, we generalize this result by showing that LIF$(G) \geq \frac{2}{r+1}n$. It was proved that for every graph $G$, $a(G) \geq \sum_{i=1}^{n}\frac{2}{d_i+1}$, where $d_1, \ldots, d_n$ is the degree sequence of $G$. Here, we conjecture that for every graph $G$ with $\delta(G) \geq 2$, LIF$(G) \geq \sum_{i=1}^{n}\frac{2}{d_i+1}$., Comment: 9 pages, 1 algorithm, 2 tables

Let $G$ be a graph with the vertex set $ \lbrace v_1,\ldots,v_n \rbrace$. The Seidel matrix of $G$ is an $n\times n$ matrix whose diagonal entries are zero, $ij$-th entry is $-1$ if $ v_{i} $ and $ v_{j} $ are adjacent and otherwise is $ 1 $. The Seidel energy of $G$ is defined to be the sum of absolute values of all eigenvalues of the Seidel matrix of $G$. Haemers conjectured that the Seidel energy of any graph of order $n$ is at least $2n-2$ and, up to Seidel equivalence, the equality holds for $ K_{n} $. We establish the validity of Haemers' Conjecture in general.

An induced path factor of a graph $G$ is a set of induced paths in $G$ with the property that every vertex of $G$ is in exactly one of the paths. The induced path number $\rho(G)$ of $G$ is the minimum number of paths in an induced path factor of $G$. We show that if $G$ is a connected cubic graph on $n>6$ vertices, then $\rho(G)\le(n-1)/3$. Fix an integer $k\ge3$. For each $n$, define $\mathcal{M}_n$ to be the maximum value of $\rho(G)$ over all connected $k$-regular graphs $G$ on $n$ vertices. As $n\rightarrow\infty$ with $nk$ even, we show that $c_k=\lim(\mathcal{M}_n/n)$ exists. We prove that $5/18\le c_3\le1/3$ and $3/7\le c_4\le1/2$ and that $c_k=\frac12-O(k^{-1})$ for $k\rightarrow\infty$., Comment: 20 pages, 3 figures

Hoffmann-Ostenhof's Conjecture states that the edge set of every connected cubic graph can be decomposed into a spanning tree, a matching and a $2$-regular subgraph. In this paper, we show that the conjecture holds for claw-free subcubic graphs and $4$-chordal subcubic graphs., Comment: 6 pages, 3 figures

A signed graph $\Gamma$ is said to be determined by its spectrum if every signed graph with the same spectrum as $\Gamma$ is switching isomorphic with $\Gamma$. Here it is proved that the path $P_n$, interpreted as a signed graph, is determined by its spectrum if and only if $n\equiv 0, 1$, or 2 (mod 4), unless $n\in\{8, 13, 14, 17, 29\}$, or $n=3$.

Let $G$ be a graph. The maximum nullity of $G$, denoted by $M(G)$, is defined to be the largest possible nullity over all real symmetric matrices $A$ whose $a_{ij}\neq 0$ for $i\neq j$, whenever two vertices $u_i$ and $u_j$ of $G$ are adjacent. In this paper, we characterize all cubic graphs with zero forcing number $3$. As a corollary, it is shown that if the zero forcing number is $3$, then $M(G)=3$. In addition, we introduce a family of cubic graphs containing graphs $G$ with $M(G)=Z(G)=4$. Also, we provide an algorithm which make a relation between maximum nullity of $G$ and the number of leaves in a spanning tree of $G$., Comment: 13 pages

A graph is equimatchable if all of its maximal matchings have the same size. A graph is claw-free if it does not have a claw as an induced subgraph. In this paper, we provide, to the best of our knowledge, the first characterization of claw-free equimatchable graphs by identifying the equimatchable claw-free graph families. This characterization implies an efficient recognition algorithm.

Let $G$ be a group. The \emph{power graph} of $G$ is a graph with the vertex set $G$, having an edge between two elements whenever one is a power of the other. We characterize nilpotent groups whose power graphs have finite independence number. For a bounded exponent group, we prove its power graph is a perfect graph and we determine its clique/chromatic number. Furthermore, it is proved that for every group $G$, the clique number of the power graph of $G$ is at most countably infinite. We also measure how close the power graph is to the \emph{commuting graph} by introducing a new graph which lies in between. We call this new graph as the \emph{enhanced power graph}. For an arbitrary pair of these three graphs we characterize finite groups for which this pair of graphs are equal.

Let $G$ be a graph whose each component has order at least 3. Let $s : E(G) \rightarrow \mathbb{Z}_k$ for some integer $k\geq 2$ be an improper edge coloring of $G$ (where adjacent edges may be assigned the same color). If the induced vertex coloring $c : V (G) \rightarrow \mathbb{Z}_k$ defined by $c(v) = \sum_{e\in E_v} s(e) \mbox{ in } \mathbb{Z}_k,$ (where the indicated sum is computed in $\mathbb{Z}_k$ and $E_v$ denotes the set of all edges incident to $v$) results in a proper vertex coloring of $G$, then we refer to such a coloring as an improper twin $k$-edge coloring. The minimum $k$ for which $G$ has an improper twin $k$-edge coloring is called the improper twin chromatic index of $G$ and is denoted by $\chi'_{it}(G)$. In this paper, we show that if $G$ is a graph with vertex chromatic number $\chi(G)$, then $\chi'_{it}(G)=\chi(G)$, unless $\chi(G)=2 \pmod 4$ and in this case $\chi'_{it}(G)\in \{\chi(G), \chi(G)+1\}$. Moreover, we show that it is NP-hard to decide whether $\chi'_{it}(G)=\chi(G)$ or $\chi'_{it}(G)=\chi(G)+1$ and give some examples of perfect graph classes for which the problem is polynomial.

Let $G$ be a graph. A total dominating set of $G$ is a set $S$ of vertices of $G$ such that every vertex is adjacent to at least one vertex in $S$. The total domatic number of a graph is the maximum number of total dominating sets which partition the vertex set of $G$. In this paper we would like to characterize the cubic graphs with total domatic number at least two., Comment: 6 pages, 5 figures

In this paper we provide some sufficient conditions for the existence of an odd or even cycle that passing a given vertex or an edge in $2$-connected or $2$-edge connected graphs. We provide some similar conditions for the existence of an odd or even circuit that passing a given vertex or an edge in 2-edge connected graphs. We show that if $G$ is a $2$-connected $k$-regular graph, $k \geq 3$, then every edge of $G$ is contained in an even cycle. We also prove that in a $2$-edge connected graph, if a vertex has odd degree, then there is an even cycle containing this vertex.

A tree containing exactly two non-pendant vertices is called a double-star. Let $k_1$ and $k_2$ be two positive integers. The double-star with degree sequence $(k_1+1, k_2+1, 1, \ldots, 1)$ is denoted by $S_{k_1, k_2}$. If $G$ is a cubic graph and has an $S$-decomposition, for a double-star $S$, then $S$ is isomorphic to $S_{1,1}$, $S_{1,2}$ or $S_{2,2}$. It is known that a cubic graph has an $S_{1,1}$-decomposition if and only if it contains a perfect matching. In this paper we study the $S_{1,2}$-decomposition of cubic graphs. First, we present some necessary conditions for the existence of an $S_{1,2}$-decomposition in cubic graphs. Then we prove that every $\{C_3, C_5, C_7\}$-free cubic graph of order $n$ with $\alpha(G)= \frac{3n}{8}$ has an $S_{1,2}$-decomposition, where $\alpha(G)$ denotes the independence number of $G$. Finally, we obtain some results on the $S_{1,r-1}$-decomposition of $r$-regular graphs., Comment: 11 Pages, 4 Figures

Recently, it has been proved that if we have a field extension, then it has linear matching property if and only if L is purely transcendental or is an extension of prime degree. In this note we provide a counterexample for this result., Comment: 2 pages

A tree containing exactly two non-pendant vertices is called a double-star. A double-star with degree sequence $(k_1+ 1, k_2+ 1, 1, \ldots, 1)$ is denoted by $S_{k_1, k_2}$. We study the edge-decomposition of regular graphs into double-stars. It was proved that every double-star of size $k$ decomposes every $2k$-regular graph. In this paper, we extend this result to $(2k+ 1)$-regular graphs, by showing that every $(2k+ 1)$-regular graph containing two disjoint perfect matchings is decomposed into $S_{k_1, k_2}$ and $S_{k_{1}-1, k_2}$, for all positive integers $k_1$ and $k_2$ such that $k_1 + k_2= k$., Comment: 10 pages, 2 figures

Let $ G $ be a graph. A subset $S \subseteq V(G) $ is called a total dominating set if every vertex of $G$ is adjacent to at least one vertex of $S$. The total domination number, $\gamma_{t}$($G$), is the minimum cardinality of a total dominating set of $G$. In this paper using a greedy algorithm we provide an upper bound for $\gamma_{t}$($G$), whenever $G$ is a bipartite graph and $\delta(G)$ $\geq$ $k$. More precisely, we show that if $k$ > 1 is a natural number, then for every bipartite graph $G$ of order $n$ and $\delta(G) \ge k$, $ $$\gamma_{t}$($G$) $\leq$ $n(1- \frac{k!}{\prod_{i=0}^{k-1}(\frac{k}{k-1}+i)}).$, Comment: 10 pages, journal

Let $R$ be a commutative ring with unity. The co-maximal ideal graph of $R$, denoted by $\Gamma(R)$, is a graph whose vertices are the proper ideals of $R$ which are not contained in the Jacobson radical of $R$, and two vertices $I_1$ and $I_2$ are adjacent if and only if $I_1 + I_2 = R$. We classify all commutative rings whose co-maximal ideal graphs are planar. In 2012 the following question was posed: If $\Gamma(R)$ is an infinite star graph, can $R$ be isomorphic to the direct product of a field and a local ring? In this paper, we give an affirmative answer to this question.

Let $R$ be a commutative ring with unity and $Z(R)$ and ${\rm Reg}(R)$ be the set of zero-divisors and non-zero zero-divisors of $R$, respectively. We denote by $T(\Gamma(R))$, the total graph of $R$, a simple graph with the vertex set $R$ and two distinct vertices $x$ and $y$ are adjacent if and only if $x+y\in Z(R)$. The induced subgraphs on $Z(R)$ and ${\rm Reg}(R)$ are denoted by $Z(\Gamma(R))$ and $Reg(\Gamma(R))$, respectively. These graphs were first introduced by D.F. Anderson and A. Badawi in 2008. In this paper, we prove the following result: let $R$ be a finite ring and one of the following conditions hold: (i) The residue field of $R$ of minimum size has even characteristic, (ii) Every residue field of $R$ has odd characteristic and $\frac{R}{J(R)}$ has no summand isomorphic to $\mathbb{Z}_3\times \mathbb{Z}_3$, then the chromatic number and clique number of $T(\Gamma(R))$ are equal to $\max\{|\mathfrak{m}|\,:\, \mathfrak{m}\in {\rm Max}(R)\}$. The same result holds for $Z(\Gamma(R))$. Moreover, if the residue field of $R$ of minimum size has even characteristic or every residue field of $R$ has odd characteristic, then we determine the chromatic number and clique number of $Reg(\Gamma(R))$ as well.

Let $R$ be a commutative ring with unity and $R^{+}$ be $Z^*(R)$ be the additive group and the set of all non-zero zero-divisors of $R$, respectively. We denote by $\mathbb{CAY}(R)$ the Cayley graph $Cay(R^+,Z^*(R))$. In this paper, we study $\mathbb{CAY}(R)$. Among other results, it is shown that for every zero-dimensional non-local ring $R$, $\mathbb{CAY}(R)$ is a connected graph of diameter 2. Moreover, for a finite ring $R$, we obtain the vertex connectivity and the edge connectivity of $\mathbb{CAY}(R)$. We investigate rings $R$ with perfect $\mathbb{CAY}(R)$ as well. We also study $Reg(\mathbb{CAY}(R))$ the induced subgraph on the regular elements of $R$. This graph gives a family of vertex transitive graphs. We show that if $R$ is a Noetherian ring and $Reg(\mathbb{CAY}(R))$ has no infinite clique, then $R$ is finite. Furthermore, for every finite ring $R$, the clique number and the chromatic number of $Reg(\mathbb{CAY}(R))$ are determined., Comment: 21 pages, 1 figure

A harmonious coloring of $G$ is a proper vertex coloring of $G$ such that every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number of $G$, $h(G)$, is the minimum number of colors needed for a harmonious coloring of $G$. We show that if $T$ is a forest of order $n$ with maximum degree $\Delta(T)\geq \frac{n+2}{3}$, then $$h(T)= \Delta(T)+2, & if $T$ has non-adjacent vertices of degree $\Delta(T)$; \Delta(T)+1, & otherwise. $$ Moreover, the proof yields a polynomial-time algorithm for an optimal harmonious coloring of such a forest., Comment: 8 pages, 1 figure

Let $G$ be a simple graph of order $n$. A dominating set of $G$ is a set $S$ of vertices of $G$ so that every vertex of $G$ is either in $S$ or adjacent to a vertex in $S$. The domination polynomial of $G$ is the polynomial $D(G,x)=\sum_{i=1}^{n} d(G,i) x^{i}$, where $d(G,i)$ is the number of dominating sets of $G$ of size $i$. In this paper we show that cycles are determined by their domination polynomials., Comment: To appear in Ars Combinatoria

Let G be a simple graph of order n. The domination polynomial of G is the polynomial D(G,x)=\sum_{i=\gamma(G)}^{n} d(G,i) x^{i}, where d(G,i) is the number of dominating sets of G of size i, and \gamma(G) is the domination number of G. In this paper we study the domination polynomials of cubic graphs of order 10. As a consequence, we show that the Petersen graph is determined uniquely by its domination polynomial., Comment: 13 pages

The energy of a graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of G. It is proved that E(G)>= 2(n-\chi(\bar{G}))>= 2(ch(G)-1) for every graph G of order n, and that E(G)>= 2ch(G) for all graphs G except for those in a few specified families, where \bar{G}, \chi(G), and ch(G) are the complement, the chromatic number, and the choice number of G, respectively., Comment: to appear in Linear Algebra and its Applications