BZPEER

preprint2026arXiv

Stability of the Strong Domination Number of Graphs

This paper introduces and studies the stability of the strong domination number of a graph, denoted $\operatorname{st}_{γ_{st}}(G)$ , defined as the minimum number of vertices whose removal changes the strong domination number $γ_{st}(G)$ . We determine exact values of this stability parameter for several fundamental graph classes, including paths, cycles, wheels, complete bipartite graphs, friendship graphs, book graphs, and balanced complete multipartite graphs. General bounds on $\operatorname{st}_{γ_{st}}(G)$ are established, along with a Nordhaus Gaddum type inequality. The behavior of stability under graph operations such as join, corona, and Cartesian product is also investigated. Structural characterizations of graphs with given stability values are provided, and several open problems and directions for future research are outlined.

preprint2022arXiv

Distinguishing threshold for some graph operations

A vertex coloring of a graph $G$ is distinguishing if non-identity automorphisms do not preserve it. The distinguishing number, $D(G)$ , is the minimum number of colors required for such a coloring and the distinguishing threshold, $θ(G)$ , is the minimum number of colors~ $k$ such that any arbitrary $k$ -coloring is distinguishing. Moreover, $Φ_k (G)$ is the number of distinguishing coloring of $G$ using at most $k$ colors. In this paper, for some graph operations, namely, vertex-sum, rooted product, corona product and lexicographic product, we find formulae of the distinguishing number and threshold using $Φ_k (G)$ .

preprint2021arXiv

Enumeration of accurate dominating sets

Let $G=(V,E)$ be a simple graph. A dominating set of $G$ is a subset $D\subseteq V$ such that every vertex not in $D$ is adjacent to at least one vertex in $D$ . The cardinality of a smallest dominating set of $G$ , denoted by $γ(G)$ , is the domination number of $G$ . A dominating set $D$ is an accurate dominating set of $G$ , if no $|D|$ -element subset of $V\setminus D$ is a dominating set of $G$ . The accurate domination number, $γ_a(G)$ , is the cardinality of a smallest accurate dominating set $D$ . In this paper, after presenting preliminaries, we count the number of accurate dominating sets of some specific graphs.

preprint2021arXiv

On the number of isolate dominating sets of certain graphs

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 $γ(G)$ , is the domination number of $G$ . A dominating set $S$ is an isolate dominating set of $G$ , if the induced subgraph $G[S]$ has at least one isolated vertex. The isolate domination number, $γ_0(G)$ , is the minimum cardinality of an isolate dominating set of $G$ . In this paper, we count the number of isolate dominating sets of some specific graphs.

preprint2021arXiv

Sombor index of certain graphs

Let $G=(V,E)$ be a finite simple graph. The Sombor index $SO(G)$ of $G$ is defined as $\sum_{uv\in E(G)}\sqrt{d_u^2+d_v^2}$ , where $d_u$ is the degree of vertex $u$ in $G$ . In this paper, we study this index for certain graphs and we examine the effects on $SO(G)$ when $G$ is modified by operations on vertex and edge of $G$ . Also we present bounds for the Sombor index of join and corona product of two graphs.

preprint2020arXiv

Introduction to dominated edge chromatic number of a graph

We introduce and study the dominated edge coloring of a graph. A dominated edge coloring of a graph $G$ is a proper edge coloring of $G$ such that each color class is dominated by at least one edge of $G$ . The minimum number of colors among all dominated edge coloring is called the dominated edge chromatic number, denoted by $χ_{dom}^{\prime}(G)$ . We obtain some properties of $χ_{dom}^{\prime}(G)$ and compute it for specific graphs. Also we examine the effects on $χ_{dom}^{\prime}(G)$ when $G$ is modified by operations on vertex and edge of $G$ . Finally, we consider the $k$ -subdivision of $G$ and study the dominated edge chromatic number of these kind of graphs.

preprint2020arXiv

On the edge chromatic vertex stability number of graphs

For an arbitrary invariant $ρ(G)$ of a graph $G$ , the $ρ-$ vertex stability number $vs_ρ(G)$ is the minimum number of vertices of $G$ whose removal results in a graph $H\subseteq G$ with $ρ(H)\neq ρ(G)$ or with $E(H)=\varnothing$ . In this paper, first we give some general lower and upper bounds for the $ρ$ -vertex stability number, and then study the edge chromatic stability number of graphs, $vs_{χ^{\prime}}(G)$ , where $χ^{\prime}=χ^{\prime}(G)$ is edge chromatic number (chromatic index) of $G$ . We prove some general results for this parameter and determine $vs_{χ^{\prime}}(G)$ for specific classes of graphs.

preprint2020arXiv

The $k$ -independent graph of a graph

Let $G=(V,E)$ be a simple graph. A set $I\subseteq V$ is an independent set, if no two of its members are adjacent in $G$ . The $k$ -independent graph of $G$ , $I_k (G)$ , is defined to be the graph whose vertices correspond to the independent sets of $G$ that have cardinality at most $k$ . Two vertices in $I_k(G)$ are adjacent if and only if the corresponding independent sets of $G$ differ by either adding or deleting a single vertex. In this paper, we obtain some properties of $I_k(G)$ and compute it for some graphs.

preprint2016arXiv

A graph which recognizes idempotents of a commutative ring

In this paper we introduce and study a graph on the set of ideals of a commutative ring $R$ . The vertices of this graph are non-trivial ideals of $R$ and two distinct ideals $I$ and $J$ are adjacent if and only $IJ=I\cap J$ . We obtain some properties of this graph and study its relation to the structure of $R$ .

preprint2016arXiv

Distinguishing number and distinguishing index of certain graphs

The distinguishing number (index) $D(G)$ ( $D'(G)$ ) of a graph $G$ is the least integer $d$ such that $G$ has an vertex labeling (edge labeling) with $d$ labels that is preserved only by a trivial automorphism. In this paper we compute these two parameters for some specific graphs. Also we study the distinguishing number and the distinguishing index of corona product of two graphs.

preprint2016arXiv

Distinguishing number and distinguishing index of graphs from primary subgraphs

The distinguishing number (index) $D(G)$ ( $D'(G)$ ) of a graph $G$ is the least integer $d$ such that $G$ has an vertex labeling (edge labeling) with $d$ labels that is preserved only by a trivial automorphism. Let $G$ be a connected graph constructed from pairwise disjoint connected graphs $G_1,\ldots ,G_k$ by selecting a vertex of $G_1$ , a vertex of $G_2$ , and identify these two vertices. Then continue in this manner inductively. We say that $G$ is obtained by point-attaching from $G_1, \ldots ,G_k$ and that $G_i$ 's are the primary subgraphs of $G$ . In this paper, we consider some particular cases of these graphs that are of importance in chemistry and study their distinguishing number and index.

preprint2016arXiv

Distinguishing number and distinguishing index of Kronecker product of two graphs

The distinguishing number (index) $D(G)$ ( $D'(G)$ ) of a graph $G$ is the least integer $d$ such that $G$ has an vertex labeling (edge labeling) with $d$ labels that is preserved only by a trivial automorphism. The Kronecker product $G\times H$ of two graphs $G$ and $H$ is the graph with vertex set $V (G)\times V (H)$ and edge set $\{\{(u, x), (v, y)\} | \{u, v\} \in E(G) ~and ~\{x, y\} \in E(H)\}$ . In this paper we study the distinguishing number and the distinguishing index of Kronecker product of two graphs.

preprint2016arXiv

Distinguishing number and distinguishing index of lexicographic product of two graphs

The distinguishing number (index) $D(G)$ ( $D'(G)$ ) of a graph $G$ is the least integer $d$ such that $G$ has an vertex labeling (edge labeling) with $d$ labels that is preserved only by a trivial automorphism. The lexicographic product of two graphs $G$ and $H$ , $G[H]$ can be obtained from $G$ by substituting a copy $H_u$ of $H$ for every vertex $u$ of $G$ and then joining all vertices of $H_u$ with all vertices of $H_v$ if $uv\in E(G)$ . In this paper we obtain some sharp bounds for the distinguishing number and the distinguishing index of lexicographic product of two graphs. As consequences, we prove that if $G$ is a connected graph with a special condition on automorphism group of $G[G]$ and $D(G)> 1$ , then for every natural $k$ , $D(G)\leq D(G^k)\leq D(G)+k-1$ , where $G^k=G[G[...]]$ . Also we prove that all lexicographic powers of $G$ , $G^k$ ( $k\geq 2$ ) can be distinguished by at most two edge labels.

preprint2016arXiv

Distinguishing number and distinguishing index of natural and fractional powers of graphs

The distinguishing number (index) $D(G)$ ( $D'(G)$ ) of a graph $G$ is the least integer $d$ such that $G$ has an vertex labeling (edge labeling) with $d$ labels that is preserved only by a trivial automorphism. For any $n \in \mathbb{N}$ , the $n$ -subdivision of $G$ is a simple graph $G^{\frac{1}{n}}$ which is constructed by replacing each edge of $G$ with a path of length $n$ . The $m^{th}$ power of $G$ , is a graph with same set of vertices of $G$ and an edge between two vertices if and only if there is a path of length at most $m$ between them. The fractional power of $G$ , denoted by $G^{\frac{m}{n}}$ is $m^{th}$ power of the $n$ -subdivision of $G$ or $n$ -subdivision of $m$ -th power of $G$ . In this paper we study the distinguishing number and distinguishing index of natural and fractional powers of $G$ . We show that the natural powers more than two of a graph distinguished by three edge labels. Also we show that for a connected graph $G$ of order $n \geqslant 3$ with maximum degree $Δ(G)$ , $D(G^{\frac{1}{k}})\leqslant min\{s: 2^k+\sum^s_{n=3}n^{k-1}\geqslant Δ(G)\}$ and for $m\geqslant 3$ , $D'(G^{\frac{m}{k}})\leqslant 3$ .

preprint2016arXiv

Distinguishing number and distinguishing index of some operations on graphs

The distinguishing number (index) $D(G)$ ( $D'(G)$ ) of a graph $G$ is the least integer $d$ such that $G$ has an vertex labeling (edge labeling) with $d$ labels that is preserved only by a trivial automorphism. We examine the effects on $D(G)$ and $D'(G)$ when $G$ is modified by operations on vertex and edge of $G$ . Let $G$ be a connected graph of order $n\geq 3$ . We show that $-1\leq D(G-v)-D(G)\leq D(G)$ , where $G-v$ denotes the graph obtained from $G$ by removal of a vertex $v$ and all edges incident to $v$ and these inequalities are true for the distinguishing index. Also we prove that $|D(G-e)-D(G)|\leq 2$ and $-1 \leq D'(G-e)-D'(G)\leq 2$ , where $G-e$ denotes the graph obtained from $G$ by simply removing the edge $e$ . Finally we consider the vertex contraction and the edge contraction of $G$ and prove that the edge contraction decrease the distinguishing number (index) of $G$ by at most one and increase by at most $3D(G)$ ( $3D'(G)$ ).

preprint2016arXiv

Domination polynomial of clique cover product of graphs

Let $G$ be a simple graph of order $n$ . 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$ . For two graphs $G$ and $H$ , let $\mathcal{C} = \{C_1,C_2, \cdots, C_k\}$ be a clique cover of $G$ and $U\subseteq V(H)$ . We consider clique cover product which denoted by $G^\mathcal{C} \star H^U$ and obtained from $G$ as follows: for each clique $C_i \in \mathcal{C}$ , add a copy of the graph $H$ and join every vertex of $C_i$ to every vertex of $U$ . We prove that the domination polynomial of clique cover product $G^\mathcal{C} \star H^{V(H)}$ or simply $G^\mathcal{C} \star H$ is $D(G^\mathcal{C} \star H,x)=\prod_{i=1}^k\Big [\big((1+x)^{n_i}-1\big)(1+x)^{|V(H)|}+D(H,x)\Big],$ where each clique $C_i \in \mathcal{C}$ has $n_i$ vertices. As results, we study the $\mathcal{D}$ -equivalence classes of some families of graphs. Also we completely describe the $\mathcal{D}$ -equivalence classes of friendship graphs constructed by coalescence $n$ copies of the cycle graph of length three with a common vertex.

preprint2016arXiv

On the roots of total domination polynomial of graphs

Let $G = (V, E)$ be a simple graph of order $n$ . The total dominating set of $G$ is a subset $D$ of $V$ that every vertex of $V$ is adjacent to some vertices of $D$ . The total domination number of $G$ is equal to minimum cardinality of total dominating set in $G$ and denoted by $γ_t(G)$ . The total domination polynomial of $G$ is the polynomial $D_t(G,x)=\sum_{i=γ_t(G)}^n d_t(G,i)$ , where $d_t(G,i)$ is the number of total dominating sets of $G$ of size $i$ . In this paper, we study roots of total domination polynomial of some graphs. We show that all roots of $D_t(G, x)$ lie in the circle with center $(-1, 0)$ and the radius $\sqrt[δ]{2^n-1}$ , where $δ$ is the minimum degree of $G$ . As a consequence we prove that if $δ\geq \frac{2n}{3}$ , then every integer root of $D_t(G, x)$ lies in the set $\{-3,-2,-1,0\}$ .

preprint2016arXiv

On the structure of dominating graphs

The $k$ -dominating graph $D_k(G)$ of a graph $G$ is defined on the vertex set consisting of dominating sets of $G$ with cardinality at most $k$ , two such sets being adjacent if they differ by either adding or deleting a single vertex. A graph is a dominating graph if it is isomorphic to $D_k(G)$ for some graph $G$ and some positive integer $k$ . Answering a question of Haas and Seyffarth for graphs without isolates, it is proved that if $G$ is such a graph of order $n\ge 2$ and with $G\cong D_k(G)$ , then $k=2$ and $G=K_{1,n-1}$ for some $n\ge 4$ . It is also proved that for a given $r$ there exist only a finite number of $r$ -regular, connected dominating graphs of connected graphs. In particular, $C_6$ and $C_8$ are the only dominating graphs in the class of cycles. Some results on the order of dominating graphs are also obtained.

preprint2016arXiv

Stabilizing on the distinguishing number of a graph

The distinguishing number $D(G)$ of a graph $G$ is the least integer $d$ such that $G$ has a vertex labeling with $d$ labels that is preserved only by a trivial automorphism. The distinguishing stability, of a graph $G$ is denoted by $st_D(G)$ and is the minimum number of vertices whose removal changes the distinguishing number. We obtain a general upper bound $st_D(G) \leqslant \vert V(G)\vert -D(G)+1$ , and a relationships between the distinguishing stabilities of graphs $G$ and $G-v$ , i.e., $st_D(G)\leqslant st_D(G-v)+1$ , where $v\in V(G)$ . Also we study the edge distinguishing stability number (distinguishing bondage number) of $G$ .

preprint2016arXiv

The distinguishing number of groups based on the distinguishing number of subgroups

Let $Γ$ be a group acting on a set $X$ . The distinguishing number for this action of $Γ$ on $X$ , denoted by $D_Γ(X)$ , is the smallest natural number $k$ such that the elements of $X$ can be labeled with $k$ labels so that any label-preserving element of $Γ$ fixes all $x \in X$ . In particular, if the action is faithful, then the only element of $Γ$ preserving labels is the identity. In this paper, we obtain an upper bound on the distinguishing number of a set knowing the distinguishing number of a set under the action of a subgroup. By the concept of motion, we obtain an upper bound for the distinguishing number of a group. Motivated by a problem (Chan 2006), we characterize $D_{Γ,H}(X)$ which is the smallest number of labels admitting a labeling of $X$ such that the only elements of $Γ$ that induce label-preserving permutations lie in $H$ . Finally, we state two algorithms for obtaining an upper and a lower bound for $D_{Γ, H}(X)$ .

preprint2016arXiv

Total domination polynomial of graphs from primary subgraphs

Let $G = (V, E)$ be a simple graph of order $n$ . The total dominating set is a subset $D$ of $V$ that every vertex of $V$ is adjacent to some vertices of $D$ . The total domination number of $G$ is equal to minimum cardinality of total dominating set in $G$ and denoted by $γ_t(G)$ . The total domination polynomial of $G$ is the polynomial $D_t(G,x)=\sum d_t(G,i)$ , where $d_t(G,i)$ is the number of total dominating sets of $G$ of size $i$ . Let $G$ be a connected graph constructed from pairwise disjoint connected graphs $G_1,\ldots ,G_k$ by selecting a vertex of $G_1$ , a vertex of $G_2$ , and identify these two vertices. Then continue in this manner inductively. We say that $G$ is obtained by point-attaching from $G_1, \ldots ,G_k$ and that $G_i$ 's are the primary subgraphs of $G$ . In this paper, we consider some particular cases of these graphs that most of them are of importance in chemistry and study their total domination polynomials.

preprint2016arXiv

Total dominator chromatic number of some operations on a graph

Let $G$ be a simple graph. A total dominator coloring of $G$ is a proper coloring of the vertices of $G$ in which each vertex of the graph is adjacent to every vertex of some color class. The total dominator chromatic number $χ_d^t(G)$ of $G$ is the minimum number of colors among all total dominator coloring of $G$ . In this paper, we examine the effects on $χ_d^t(G)$ when $G$ is modified by operations on vertex and edge of $G$ .

preprint2016arXiv

Trees with distinguishing number two

The distinguishing number $D(G)$ of a graph $G$ is the least integer $d$ such that $G$ has a vertex labeling with $d$ labels that is preserved only by a trivial automorphism. In this paper we characterize all trees with radius at most three and distinguishing number two. Also we present a necessary condition for trees with distinguishing number two and radius more than three.

preprint2015arXiv

Domination polynomial of generalized friendship and generalized book graphs

Let G be a simple graph of order n. The domination polynomial of a graph is the generating function of its dominating sets. We study the domination polynomials of generalized friendship graphs. We also consider book graphs formed by joining n copies of the cycle graph of order 4 with a common edge and study the domination polynomials of some generalized book graphs. In particular we examine the domination roots of these families and find the limiting curve for the roots.

preprint2015arXiv

Domination polynomial of lexicographic product of specific graphs

Let $G$ be a simple graph of order $n$ . The domination polynomial of $G$ is the polynomial $D(G,λ)=\sum_{i=0}^{n} d(G,i) λ^{i}$ , where $d(G,i)$ is the number of dominating sets of $G$ of size $i$ . We consider the lexicographic product of two specific graphs and study their domination polynomials.

preprint2015arXiv

On $\mathcal{D}$ -equivalence classes of some graphs

Let $G$ be a simple graph of order $n$ . 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$ . The $n$ -barbell graph $Bar_n$ with $2n$ vertices, is formed by joining two copies of a complete graph $K_n$ by a single edge. We prove that for every $n\geq 2$ , $Bar_n$ is not $\mathcal{D}$ -unique, that is, there is another non-isomorphic graph with the same domination polynomial. More precisely, we show that for every $n$ , the $\mathcal{D}$ -equivalence class of barbell graph, $[Bar_n]$ , contains many graphs, which one of them is the complement of book graph of order $n-1$ , $B_{n-1}^c$ . Also we present many families of graphs in $\mathcal{D}$ -equivalence class of $K_{n_1}\cup K_{n_2}\cup \cdots\cup K_{n_k}$ .

preprint2015arXiv

On the $n-$ dominating graph of specific graphs

Let $G=(V,E)$ be a graph. A set $S\subseteq V(G)$ is a dominating set, if every vertex in $V(G)\backslash S$ is adjacent to at least one vertex in $S$ . The $k$ -dominating graph of $G$ , $D_k (G)$ , is defined to be the graph whose vertices correspond to the dominating sets of $G$ that have cardinality at most $k$ . Two vertices in $D_k(G)$ are adjacent if and only if the corresponding dominating sets of $G$ differ by either adding or deleting a single vertex. In this paper we consider and study the $n$ -dominating graph of specific graphs.

preprint2015arXiv

Total dominator chromatic number of specific graphs

Let $G$ be a simple graph. A total dominator coloring of $G$ is a proper coloring of the vertices of $G$ in which each vertex of the graph is adjacent to every vertex of some color class. The total dominator chromatic number $χ_d^t(G)$ of $G$ is the minimum number of colors among all total dominator coloring of $G$ . In this paper, we study the total dominator chromatic number of some specific graphs.

preprint2014arXiv

An atlas of domination polynomials of graphs of order at most six

The domination polynomial of a graph $G$ of order $n$ is the polynomial $D(G,x)=\sum_{i=γ(G)}^{n} d(G,i) x^{i}$ , where $d(G,i)$ is the number of dominating sets of $G$ of size $i$ , and $γ(G)$ is the domination number of $G$ . The roots of domination polynomial is called domination roots. In this article, we compute the domination polynomial and domination roots of all graphs of order less than or equal to 6, and show them in the tables.

preprint2014arXiv

Final title: "More on domination polynomial and domination root" Previous title: "Graphs with domination roots in the right half-plane"

Let $G$ be a simple graph of order n. The domination polynomial of G is the polynomial D(G,x) =\sum d(G, i)x^i, where d(G,i) is the number of dominating sets of G of size i. Every root of D(G,x) is called the domination root of G. It is clear that (0,\infty) is zero free interval for domination polynomial of a graph. It is interesting to investigate graphs which have complex domination roots with positive real parts. In this paper, we first investigate complexity of the domination polynomial at specific points. Then we present and investigate some families of graphs whose complex domination roots have positive real part.

preprint2014arXiv

More on energy and Randic energy of specific graphs

Let $G$ be a simple graph of order $n$ . The energy $E(G)$ of the graph $G$ is the sum of the absolute values of the eigenvalues of $G$ . The Randić matrix of $G$ , denoted by $R(G)$ , is defined as the $n\times n$ matrix whose $(i,j)$ -entry is $(d_id_j)^{\frac{-1}{2}}$ if $v_i$ and $v_j$ are adjacent and $0$ for another cases. The Randić energy $RE$ of $G$ is the sum of absolute values of the eigenvalues of $R(G)$ . In this paper we compute the energy and Randić energy for certain graphs. Also we propose a conjecture on Randić energy.

preprint2014arXiv

On the domination polynomials of cactus chains

Let $G$ be a simple graph of order $n$ . The domination polynomial of $G$ is the polynomial $D(G, x)=\sum_{i=γ(G)}^{n} d(G,i) x^{i}$ , where $d(G,i)$ is the number of dominating sets of $G$ of size $i$ and $γ(G)$ is the domination number of $G$ . In this paper we consider cactus chains with triangular and square blocks and study their domination polynomials.

preprint2014arXiv

On the Domination Polynomials of Friendship Graphs

Let $G$ be a simple graph of order $n$ . The {\em domination polynomial} of $G$ is the polynomial ${D(G, x)=\sum_{i=0}^{n} d(G,i) x^{i}}$ , where $d(G,i)$ is the number of dominating sets of $G$ of size $i$ . Let $n$ be any positive integer and $F_n$ be the Friendship graph with $2n + 1$ vertices and $3n$ edges, formed by the join of $K_{1}$ with $nK_{2}$ . We study the domination polynomials of this family of graphs, and in particular examine the domination roots of the family, and find the limiting curve for the roots. We also show that for every $n\geq 2$ , $F_n$ is not $\mathcal{D}$ -unique, that is, there is another non-isomorphic graph with the same domination polynomial. Also we construct some families of graphs whose real domination roots are only $-2$ and $0$ . Finally, we conclude by discussing the domination polynomials of a related family of graphs, the $n$ -book graphs $B_n$ , formed by joining $n$ copies of the cycle graph $C_4$ with a common edge.

preprint2014arXiv

Randic energy of specific graphs

Let $G$ be a simple graph with vertex set $V(G) = \{v_1, v_2,..., v_n\}$ . The Randić matrix of $G$ , denoted by $R(G)$ , is defined as the $n\times n$ matrix whose $(i,j)$ -entry is $(d_id_j)^{\frac{-1}{2}}$ if $v_i$ and $v_j$ are adjacent and $0$ for another cases. Let the eigenvalues of the Randić matrix $R(G)$ be $ρ_1\geq ρ_2\geq ...\geq ρ_n$ which are the roots of the Randić characteristic polynomial $\prod_{i=1}^n (ρ-ρ_i)$ . The Randić energy $RE$ of $G$ is the sum of absolute values of the eigenvalues of $R(G)$ . In this paper we compute the Randić characteristic polynomial and the Randić energy for specific graphs $G$ .

preprint2014arXiv

Some families of graphs whose domination polynomials are unimodal

Let $G$ be a simple graph of order $n$ . The domination polynomial of $G$ is the polynomial $D(G, x)=\sum_{i=γ(G)}^{n} d(G,i) x^{i}$ , where $d(G,i)$ is the number of dominating sets of $G$ of size $i$ and $γ(G)$ is the domination number of $G$ . It is conjectured that the domination polynomial of any graph is unimodal. In this paper we present some families of graphs whose domination polynomials are unimodal.

preprint2014arXiv

The edge cover polynomials of cubic graphs of order 10

Let $G$ be a simple graph of order $n$ and size $m$ . The edge covering of $G$ is a set of edges such that every vertex of $G$ is incident to at least one edge of the set. The edge cover polynomial of $G$ is the polynomial $E(G,x)=\sum_{i=ρ(G)}^{m} e(G,i) x^{i}$ , where $e(G,i)$ is the number of edge coverings of $G$ of size $i$ , and $ρ(G)$ is the edge covering number of $G$ . In this paper we study the edge cover polynomials of cubic graphs of order $10$ . We show that all cubic graphs of order $10$ (especially the Petersen graph) are determined uniquely by their edge cover polynomials. Also we construct infinite families of graphs whose edge cover polynomials have only roots $-1$ and $0$ .

preprint2013arXiv

Independent sets of some graphs associated to commutative rings

Let $G=(V,E)$ be a simple graph. A set $S\subseteq V$ is independent set of $G$ , if no two vertices of $S$ are adjacent. The independence number $α(G)$ is the size of a maximum independent set in the graph. %An independent set with cardinality Let $R$ be a commutative ring with nonzero identity and $I$ an ideal of $R$ . The zero-divisor graph of $R$ , denoted by $Γ(R)$ , is an undirected graph whose vertices are the nonzero zero-divisors of $R$ and two distinct vertices $x$ and $y$ are adjacent if and only if $xy = 0$ . Also the ideal-based zero-divisor graph of $R$ , denoted by $Γ_I(R)$ , is the graph which vertices are the set ${x\in R\backslash I | xy\in I \quad for some \quad y\in R\backslash I\}$ and two distinct vertices $x$ and $y$ are adjacent if and only if $xy \in I$ . In this paper we study the independent sets and the independence number of $Γ(R)$ and $Γ_I(R)$ .

preprint2012arXiv

On the k-edge magic graphs

Let $G$ be a graph with vertex set V and edge set E such that |V| = p and |E| = q. For integers k\geq 0, define an edge labeling f : E \rightarrow \{k,k+1,....,k+q-1\} and define the vertex sum for a vertex $v$ as the sum of the labels of the edges incident to v. If such an edge labeling induces a vertex labeling in which every vertex has a constant vertex sum (mod p), then G is said to be k-edge magic (k-EM). In this paper, we (i) show that all the maximal outerplanar graphs of order p = 4; 5; 7 are k-EM if and only if k\equiv 2 (mod p); (ii) obtain all the maximal outerplanar graphs that are k-EM for k = 3; 4; and (iii) characterize all (p; p-h)-graph that are k-EM for h\geq 0. We conjecture that all maximal outerplanar graphs of prime order p are k-EM if and only if k \equiv 2 (mod p).

preprint2012arXiv

Some new results on domination roots of a graph

Let $G$ be a simple graph of order $n$ . The domination polynomial of $G$ is the polynomial $D(G,λ)=\sum_{i=0}^{n} d(G,i) λ^{i}$ , where $d(G,i)$ is the number of dominating sets of $G$ of size $i$ . Every root of $D(G,λ)$ is called the domination root of $G$ . We present families of graphs whose their domination polynomial have no nonzero real roots. We observe that these graphs have complex domination roots with positive real part. Then, we consider the lexicographic product of two graphs and obtain a formula for domination polynomial of this product. Using this product, we construct a family of graphs which their domination roots are dense in all of $\mathbb{C}$ .

preprint2011arXiv

Graphs which their certain polynomials have few distinct roots- a survey

Let G = (V;E) be a simple graph. We consider domination polynomial, matching polynomial and edge cover polynomial of G. Graphs which their polynomials have few roots can give sometimes a very surprising information about the structure of the graph. In this paper we study graphs which their domination polynomial, independence polynomial and edge cover polynomial have few roots.

Saeid Alikhani

Research overview

Is this your work?

40 publications

Stability of the Strong Domination Number of Graphs

Distinguishing threshold for some graph operations

Enumeration of accurate dominating sets

On the number of isolate dominating sets of certain graphs

Sombor index of certain graphs

Introduction to dominated edge chromatic number of a graph

On the edge chromatic vertex stability number of graphs

The kkk-independent graph of a graph

A graph which recognizes idempotents of a commutative ring

Distinguishing number and distinguishing index of certain graphs

Distinguishing number and distinguishing index of graphs from primary subgraphs

Distinguishing number and distinguishing index of Kronecker product of two graphs

Distinguishing number and distinguishing index of lexicographic product of two graphs

Distinguishing number and distinguishing index of natural and fractional powers of graphs

Distinguishing number and distinguishing index of some operations on graphs

Domination polynomial of clique cover product of graphs

On the roots of total domination polynomial of graphs

On the structure of dominating graphs

Stabilizing on the distinguishing number of a graph

The distinguishing number of groups based on the distinguishing number of subgroups

Total domination polynomial of graphs from primary subgraphs

Total dominator chromatic number of some operations on a graph

Trees with distinguishing number two

Domination polynomial of generalized friendship and generalized book graphs

Domination polynomial of lexicographic product of specific graphs

On D\mathcal{D}D-equivalence classes of some graphs

On the n−n-n−dominating graph of specific graphs

Total dominator chromatic number of specific graphs

An atlas of domination polynomials of graphs of order at most six

Final title: "More on domination polynomial and domination root" Previous title: "Graphs with domination roots in the right half-plane"

More on energy and Randic energy of specific graphs

On the domination polynomials of cactus chains

On the Domination Polynomials of Friendship Graphs

Randic energy of specific graphs

Some families of graphs whose domination polynomials are unimodal

The edge cover polynomials of cubic graphs of order 10

Independent sets of some graphs associated to commutative rings

On the k-edge magic graphs

Some new results on domination roots of a graph

Graphs which their certain polynomials have few distinct roots- a survey

See the researcher in context

Building this map preview

The $k$ -independent graph of a graph

On $\mathcal{D}$ -equivalence classes of some graphs

On the $n-$ dominating graph of specific graphs