-
Spectral Methods for Matrix Product Factorization
Authors:
Saieed Akbari,
Yi-Zheng Fan,
Fu-Tao Hu,
Babak Miraftab,
Yi Wang
Abstract:
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…
▽ More
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.
△ Less
Submitted 4 July, 2024;
originally announced July 2024.
-
Line graphs and Nordhaus-Gaddum-type bounds for self-loop graphs
Authors:
Saieed Akbari,
Irena M. Jovanović,
Johnny Lim
Abstract:
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 po…
▽ More
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 $δ(G),$ as well as proving two Nordhaus-Gaddum-type bounds for the spectral radius and the energy of $G_S,$ respectively.
△ Less
Submitted 15 May, 2024;
originally announced May 2024.
-
On the $Δ$-edge stability number of graphs
Authors:
Saieed Akbari,
Reza Hosseini Dolatabadi,
Mohsen Jamaali,
Sandi Klavžar,
Nazanin Movarraei
Abstract:
The $Δ$-edge stability number ${\rm es}_Δ(G)$ of a graph $G$ is the minimum number of edges of $G$ whose removal results in a subgraph $H$ with $Δ(H) = Δ(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 wh…
▽ More
The $Δ$-edge stability number ${\rm es}_Δ(G)$ of a graph $G$ is the minimum number of edges of $G$ whose removal results in a subgraph $H$ with $Δ(H) = Δ(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}_Δ(G) \leq c |V(G)|$ for an arbitrary graph $G$ of given maximum degree $Δ$, where $c$ is a given constant, it suffices to prove the bound for $Δ$-regular graphs. Sharp upper bounds of this form are derived for regular graphs. It is proved that if $Δ(G) \geq\frac{|V(G)|-2}{3}$ or the induced subgraph on maximum degree vertices has a $Δ(G)$-edge coloring, then ${\rm es}_Δ(G) \le |V(G)|/2$.
△ Less
Submitted 8 March, 2024;
originally announced March 2024.
-
Lower bounds for the Randić index in terms of matching number
Authors:
Saieed Akbari,
Sina Ghasemi Nezhad,
Reyhane Ghazizadeh,
John Haslegrave,
Elahe Tohidi
Abstract:
We investigate how small the Randić 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,…
▽ More
We investigate how small the Randić 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ć index for graphs with a near perfect matching, and conjecture that the same bounds hold for all graphs.
△ Less
Submitted 20 February, 2024;
originally announced February 2024.
-
2-Coupon Coloring of Cubic Graphs Containing 3-Cycle or 4-Cycle
Authors:
S. Akbari,
M. Azimian,
A. Fazli Khani,
B. Samimi,
E. Zahiri
Abstract:
Let $G$ be a graph. A total dominating set in a graph $G$ is a set $S$ of vertices of $G$ such that every vertex in $G$ is adjacent to a vertex in $S$. Recently, the following question was proposed: "Is it true that every connected cubic graph containing a $3$-cycle has two vertex disjoint total dominating sets?" In this paper, we give a negative answer to this question. Moreover, we prove that if…
▽ More
Let $G$ be a graph. A total dominating set in a graph $G$ is a set $S$ of vertices of $G$ such that every vertex in $G$ is adjacent to a vertex in $S$. Recently, the following question was proposed: "Is it true that every connected cubic graph containing a $3$-cycle has two vertex disjoint total dominating sets?" In this paper, we give a negative answer to this question. Moreover, we prove that if we replace $3$-cycle with $4$-cycle the answer is affirmative. This implies every connected cubic graph containing a diamond (the complete graph of order $4$ minus one edge) as a subgraph can be partitioned into two total dominating sets, a result that was proved in 2017.
△ Less
Submitted 29 August, 2023;
originally announced August 2023.
-
Some Results On Spectrum And Energy Of Graphs With Loops
Authors:
Saieed Akbari,
Hussah Al Menderj,
Miin Huey Ang,
Johnny Lim,
Zhen Chuan Ng
Abstract:
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 ident…
▽ More
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$.
△ Less
Submitted 11 April, 2023;
originally announced April 2023.
-
End Super Dominating Sets in Graphs
Authors:
Saieed Akbari,
Nima Ghanbari,
Michael A. Henning
Abstract:
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$. Two vertices are neighbors if they are adjacent. A super dominating set is a dominating set $S$ with the additional property that ever…
▽ More
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$. 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.
△ Less
Submitted 14 November, 2022; v1 submitted 7 September, 2022;
originally announced September 2022.
-
A lower bound of the energy of non-singular graphs in terms of average degree
Authors:
Saieed Akbari,
Hossein Dabirian,
S. Mahmood Ghasemi
Abstract:
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Δ(G)+δ(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 de…
▽ More
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Δ(G)+δ(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$
△ Less
Submitted 10 July, 2022;
originally announced July 2022.
-
Tight Bounds on the Chromatic Edge Stability Index of Graphs
Authors:
Saieed Akbari,
John Haslegrave,
Mehrbod Javadi,
Nasim Nahvi,
Helia Niaparast
Abstract:
The chromatic edge stability index $\mathrm{es}_{χ'}(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}_{χ'}(G)$ in terms of the number of vertices of degree $Δ(G)$ (if $G$ is Class 2), and the numbers of vertices of degree $Δ(G)$ and ${Δ(G)-1}$ (if $G$ is Class 1). If $G$ is bipartite…
▽ More
The chromatic edge stability index $\mathrm{es}_{χ'}(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}_{χ'}(G)$ in terms of the number of vertices of degree $Δ(G)$ (if $G$ is Class 2), and the numbers of vertices of degree $Δ(G)$ and ${Δ(G)-1}$ (if $G$ is Class 1). If $G$ is bipartite we give an exact expression for $\mathrm{es}_{χ'}(G)$ involving the maximum size of a matching in the subgraph induced by vertices of degree $Δ(G)$. Finally, we consider whether a minimum mitigating set, that is a set of size $\mathrm{es}_{χ'}(G)$ whose removal reduces the chromatic index, has the property that every edge meets a vertex of degree at least $Δ(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$.
△ Less
Submitted 21 December, 2023; v1 submitted 8 June, 2022;
originally announced June 2022.
-
A bound for the $p$-domination number of a graph in terms of its eigenvalue multiplicities
Authors:
A. Abiad,
S. Akbari,
M. H. Fakharan,
A. Mehdizadeh
Abstract:
Let $G$ be a connected graph of order $n$ with domination number $γ(G)$. Wang, Yan, Fang, Geng and Tian [Linear Algebra Appl. 607 (2020), 307-318] showed that for any Laplacian eigenvalue $λ$ of $G$ with multiplicity $m_G(λ)$, it holds that $γ(G)\leq n-m_G(λ)$. Using techniques from the theory of star sets, in this work we prove that the same bound holds when $λ$ is an arbitrary adjacency eigenval…
▽ More
Let $G$ be a connected graph of order $n$ with domination number $γ(G)$. Wang, Yan, Fang, Geng and Tian [Linear Algebra Appl. 607 (2020), 307-318] showed that for any Laplacian eigenvalue $λ$ of $G$ with multiplicity $m_G(λ)$, it holds that $γ(G)\leq n-m_G(λ)$. Using techniques from the theory of star sets, in this work we prove that the same bound holds when $λ$ is an arbitrary adjacency eigenvalue of a non-regular graph, and we characterize the cases of equality. Moreover, we show a result that gives a relationship between start sets and the $p$-domination number, and we apply it to extend the aforementioned spectral bound to the $p$-domination number using the adjacency and Laplacian eigenvalue multiplicities.
△ Less
Submitted 13 September, 2021;
originally announced September 2021.
-
On the Chromatic Vertex Stability Number of Graphs
Authors:
Saieed Akbari,
Arash Beikmohammadi,
Sandi Klavžar,
Nazanin Movarraei
Abstract:
The chromatic vertex (resp.\ edge) stability number ${\rm vs}_χ(G)$ (resp.\ ${\rm es}_χ(G)$) of a graph $G$ is the minimum number of vertices (resp.\ edges) whose deletion results in a graph $H$ with $χ(H)=χ(G)-1$. In the main result it is proved that if $G$ is a graph with $χ(G) \in \{ Δ(G), Δ(G)+1 \}$, then ${\rm vs}_χ(G) = {\rm ivs}_χ(G)$, where ${\rm ivs}_χ(G)$ is the independent chromatic ver…
▽ More
The chromatic vertex (resp.\ edge) stability number ${\rm vs}_χ(G)$ (resp.\ ${\rm es}_χ(G)$) of a graph $G$ is the minimum number of vertices (resp.\ edges) whose deletion results in a graph $H$ with $χ(H)=χ(G)-1$. In the main result it is proved that if $G$ is a graph with $χ(G) \in \{ Δ(G), Δ(G)+1 \}$, then ${\rm vs}_χ(G) = {\rm ivs}_χ(G)$, where ${\rm ivs}_χ(G)$ is the independent chromatic vertex stability number. The result need not hold for graphs $G$ with $χ(G) \le \frac{Δ(G)+1}{2}$. It is proved that if $χ(G) > \frac{Δ(G)}{2}+1$, then ${\rm vs}_χ(G) = {\rm es}_χ(G)$. A Nordhaus-Gaddum-type result on the chromatic vertex stability number is also given.
△ Less
Submitted 14 December, 2021; v1 submitted 30 August, 2021;
originally announced August 2021.
-
On the chromatic edge stability index of graphs
Authors:
Saieed Akbari,
Arash Beikmohammadi,
Boštjan Brešar,
Tanja Dravec,
Mohammad Mahdi Habibollahi,
Nazanin Movarraei
Abstract:
Given a non-trivial graph $G$, the minimum cardinality of a set of edges $F$ in $G$ such that $χ'(G \setminus F)<χ'(G)$ is called the chromatic edge stability index of $G$, denoted by $es_{χ'}(G)$, and such a (smallest) set $F$ is called a (minimum) mitigating set. While $1\le es_{χ'}(G)\le \lfloor n/2\rfloor$ holds for any graph $G$, we investigate the graphs with extremal and near-extremal value…
▽ More
Given a non-trivial graph $G$, the minimum cardinality of a set of edges $F$ in $G$ such that $χ'(G \setminus F)<χ'(G)$ is called the chromatic edge stability index of $G$, denoted by $es_{χ'}(G)$, and such a (smallest) set $F$ is called a (minimum) mitigating set. While $1\le es_{χ'}(G)\le \lfloor n/2\rfloor$ holds for any graph $G$, we investigate the graphs with extremal and near-extremal values of $es_{χ'}(G)$. The graphs $G$ with $es_{χ'}(G)=\lfloor n/2\rfloor$ are classified, and the graphs $G$ with $es_{χ'}(G)=\lfloor n/2\rfloor-1$ and $χ'(G)=Δ(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_{χ'}(G)=1$. We also prove that every minimum mitigating set of an $r$-regular graph $G$, where $r\ne 4$, with $es_{χ'}(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_{χ'}(G)\in\{1,2,\lfloor n/2\rfloor-1,\lfloor n/2\rfloor\}$, and for bipartite graphs.
△ Less
Submitted 24 August, 2021;
originally announced August 2021.
-
Spectra of strongly Deza graphs
Authors:
Saieed Akbari,
Willem H. Haemers,
Mohammad Ali Hosseinzadeh,
Vladislav V. Kabanov,
Elena V. Konstantinova,
Leonid Shalaginov
Abstract:
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 gra…
▽ More
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.
△ Less
Submitted 18 January, 2021;
originally announced January 2021.
-
Zero-sum flows for Steiner systems
Authors:
Saieed Akbari,
Hamid Reza Maimani,
Leila Parsaei Majd,
Ian M. Wanless
Abstract:
Given a $t$-$(v, k, λ)$ 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…
▽ More
Given a $t$-$(v, k, λ)$ 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.
△ Less
Submitted 4 January, 2021;
originally announced January 2021.
-
On a question of Haemers regarding vectors in the nullspace of Seidel matrices
Authors:
Saieed Akbari,
Sebastian M. Cioabă,
Samira Goudarzi,
Aidin Niaparast,
Artin Tajdini
Abstract:
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…
▽ More
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.
△ Less
Submitted 21 January, 2021; v1 submitted 12 November, 2020;
originally announced November 2020.
-
Independent Domination in Subcubic Graphs
Authors:
A. Akbari,
S. Akbari,
A. Doosthosseini,
Z. Hadizadeh,
Michael A. Henning,
A. Naraghi
Abstract:
A set $S$ of vertices in a graph $G$ is a dominating set if every vertex not in $S$ is adjacent to a vertex in $S$. If, in addition, $S$ is an independent set, then $S$ is an independent dominating set. The independent domination number $i(G)$ of $G$ is the minimum cardinality of an independent dominating set in $G$. In 2013 Goddard and Henning [Discrete Math 313 (2013), 839--854] conjectured that…
▽ More
A set $S$ of vertices in a graph $G$ is a dominating set if every vertex not in $S$ is adjacent to a vertex in $S$. If, in addition, $S$ is an independent set, then $S$ is an independent dominating set. The independent domination number $i(G)$ of $G$ is the minimum cardinality of an independent dominating set in $G$. In 2013 Goddard and Henning [Discrete Math 313 (2013), 839--854] conjectured that if $G$ is a connected cubic graph of order $n$, then $i(G) \le \frac{3}{8}n$, except if $G$ is the complete bipartite graph $K_{3,3}$ or the $5$-prism $C_5 \, \Box \, K_2$. Further they construct two infinite families of connected cubic graphs with independent domination three-eighths their order. They remark that perhaps it is even true that for $n > 10$ these two families are only families for which equality holds. In this paper, we provide a new family of connected cubic graphs $G$ of order $n$ such that $i(G) = \frac{3}{8}n$. We also show that if $G$ is a subcubic graph of order $n$ with no isolated vertex, then $i(G) \le \frac{1}{2}n$, and we characterize the graphs achieving equality in this bound.
△ Less
Submitted 9 January, 2020;
originally announced January 2020.
-
Some Results on Dominating Induced Matchings
Authors:
Saieed Akbari,
Hossein Baktash,
Amin Behjati,
Afshin Behmaram,
Mohammad Roghani
Abstract:
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 $χ(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 s…
▽ More
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 $χ(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$.
△ Less
Submitted 1 December, 2019;
originally announced December 2019.
-
A Note on Induced Path Decomposition of Graphs
Authors:
S. Akbari,
H. R. Maimani,
A. Seify
Abstract:
Let $G$ be a graph of order $n$. The path decomposition of $G$ is a set of disjoint paths, say $\mathcal{P}$, which cover all vertices of $G$. If all paths are induced paths in $G$, then we say $\mathcal{P}$ is an induced path decomposition of $G$. Moreover, if every path is of order at least 2, then we say $G$ has an IPD. In this paper, we prove that every connected $r$-regular graph which is not…
▽ More
Let $G$ be a graph of order $n$. The path decomposition of $G$ is a set of disjoint paths, say $\mathcal{P}$, which cover all vertices of $G$. If all paths are induced paths in $G$, then we say $\mathcal{P}$ is an induced path decomposition of $G$. Moreover, if every path is of order at least 2, then we say $G$ has an IPD. In this paper, we prove that every connected $r$-regular graph which is not complete graph of odd order admits an IPD. Also we show that every connected bipartite cubic graph of order $n$ admits an IPD of size at most $\frac{n}{3}$. We classify all connected claw-free graphs which admit an IPD.
△ Less
Submitted 1 December, 2019;
originally announced December 2019.
-
On the Maximum Order of Induced Paths and Induced Forests in Regular Graphs
Authors:
Saieed Akbari,
Alireza Amanihamedani,
Sepehr Mousavi,
Hesam Nikpey,
Soheil Sheybani
Abstract:
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$,…
▽ More
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 $δ(G) \geq 2$, LIF$(G) \geq \sum_{i=1}^{n}\frac{2}{d_i+1}$.
△ Less
Submitted 6 November, 2019;
originally announced November 2019.
-
Trees with a large Laplacian eigenvalue multiplicity
Authors:
S. Akbari,
E. R. van Dam,
M. H. Fakharan
Abstract:
In this paper, we study the multiplicity of the Laplacian eigenvalues of trees. It is known that for trees, integer Laplacian eigenvalues larger than $1$ are simple and also the multiplicity of Laplacian eigenvalue $1$ has been well studied before. Here we consider the multiplicities of the other (non-integral) Laplacian eigenvalues. We give an upper bound and determine the trees of order $n$ that…
▽ More
In this paper, we study the multiplicity of the Laplacian eigenvalues of trees. It is known that for trees, integer Laplacian eigenvalues larger than $1$ are simple and also the multiplicity of Laplacian eigenvalue $1$ has been well studied before. Here we consider the multiplicities of the other (non-integral) Laplacian eigenvalues. We give an upper bound and determine the trees of order $n$ that have a multiplicity that is close to the upper bound $\frac{n-3}{2}$, and emphasize the particular role of the algebraic connectivity.
△ Less
Submitted 23 October, 2019; v1 submitted 26 July, 2019;
originally announced July 2019.
-
Star Coloring of the Cartesian Product of Cycles
Authors:
S Akbari,
M Chavooshi,
M Ghanbari,
S Taghian
Abstract:
A proper vertex coloring of a graph $G$ is called a star coloring if every two color classes induce a forest whose each component is a star, which means there is no bicolored $P_4$ in $G$. In this paper, we show that the Cartesian product of any two cycles, except $C_3 \square C_3$ and $C_3 \square C_5$, has a $5$-star coloring.
A proper vertex coloring of a graph $G$ is called a star coloring if every two color classes induce a forest whose each component is a star, which means there is no bicolored $P_4$ in $G$. In this paper, we show that the Cartesian product of any two cycles, except $C_3 \square C_3$ and $C_3 \square C_5$, has a $5$-star coloring.
△ Less
Submitted 15 June, 2019;
originally announced June 2019.
-
Well-indumatched Trees and Graphs of Bounded Girth
Authors:
S. Akbari,
T. Ekim,
A. H. Ghodrati,
S. Zare
Abstract:
A graph G is called well-indumatched if all of its maximal induced matchings have the same size. In this paper we characterize all well-indumatched trees. We provide a linear time algorithm to decide if a tree is well-indumatched or not. Then, we characterize minimal well-indumatched graphs of girth at least 9 and show subsequently that for an odd integer g greater than or equal to 9 and different…
▽ More
A graph G is called well-indumatched if all of its maximal induced matchings have the same size. In this paper we characterize all well-indumatched trees. We provide a linear time algorithm to decide if a tree is well-indumatched or not. Then, we characterize minimal well-indumatched graphs of girth at least 9 and show subsequently that for an odd integer g greater than or equal to 9 and different from 11, there is no well-indumatched graph of girth g. On the other hand, there are infinitely many well-indumatched unicyclic graphs of girth k, where k is in {3, 5, 7} or k is an even integer greater than 2. We also show that, although the recognition of well-indumatched graphs is known to be co-NP-complete in general, one can recognize in polynomial time well-indumatched graphs where the size of maximal induced matchings is fixed.
△ Less
Submitted 16 December, 2019; v1 submitted 7 March, 2019;
originally announced March 2019.
-
Proof of a Conjecture on the Seidel Energy of Graphs
Authors:
Saieed Akbari,
Mostafa Einollahzadeh,
Mohammad Mahdi Karkhaneei,
Mohammad Ali Nematollahi
Abstract:
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 ener…
▽ More
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.
△ Less
Submitted 20 January, 2019;
originally announced January 2019.
-
Induced path factors of regular graphs
Authors:
Saieed Akbari,
Daniel Horsley,
Ian M. Wanless
Abstract:
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 $ρ(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 $ρ(G)\le(n-1)/3$.
Fix an integer $k\ge3$. For each $n$, define…
▽ More
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 $ρ(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 $ρ(G)\le(n-1)/3$.
Fix an integer $k\ge3$. For each $n$, define $\mathcal{M}_n$ to be the maximum value of $ρ(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$.
△ Less
Submitted 1 November, 2020; v1 submitted 12 September, 2018;
originally announced September 2018.
-
Decomposing Claw-free Subcubic Graphs and $4$-Chordal Subcubic Graphs
Authors:
Elham Aboomahigir,
Milad Ahanjideh,
Saieed Akbari
Abstract:
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.
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.
△ Less
Submitted 30 January, 2020; v1 submitted 28 June, 2018;
originally announced June 2018.
-
The Algebraic Connectivity of a Graph and its Complement
Authors:
B. Afshari,
S. Akbari,
M. J. Moghaddamzadeh,
B. Mohar
Abstract:
For a graph $G$, let $λ_2(G)$ denote its second smallest Laplacian eigenvalue. It was conjectured that $λ_2(G) + λ_2(\overline G) \ge 1$, where $\overline G$ is the complement of $G$. In this paper, it is shown that $\max\{λ_2(G), λ_2(\overline G)\} \ge 2/5$.
For a graph $G$, let $λ_2(G)$ denote its second smallest Laplacian eigenvalue. It was conjectured that $λ_2(G) + λ_2(\overline G) \ge 1$, where $\overline G$ is the complement of $G$. In this paper, it is shown that $\max\{λ_2(G), λ_2(\overline G)\} \ge 2/5$.
△ Less
Submitted 18 June, 2018;
originally announced June 2018.
-
Some Mixed Graphs Determined by Their Spectrum
Authors:
S. Akbari,
A. Ghafari,
M. Nahvi,
M. A. Nematollahi
Abstract:
A mixed graph is obtained from a graph by orienting some of its edges. The Hermitian adjacency matrix of a mixed graph with the vertex set $ \{v_{1}, \ldots , v_{n}\} $, is the matrix $ H=[h_{ij}]_{n \times n} $, where $ h_{ij}=-h_{ji}=i $ if there is a directed edge from $ v_{i} $ to $ v_{j} $, $ h_{ij}=1 $ if there exists an undirected edge between $v_i$ and $v_{j}$, and $h_{ij}=0$ otherwise. Th…
▽ More
A mixed graph is obtained from a graph by orienting some of its edges. The Hermitian adjacency matrix of a mixed graph with the vertex set $ \{v_{1}, \ldots , v_{n}\} $, is the matrix $ H=[h_{ij}]_{n \times n} $, where $ h_{ij}=-h_{ji}=i $ if there is a directed edge from $ v_{i} $ to $ v_{j} $, $ h_{ij}=1 $ if there exists an undirected edge between $v_i$ and $v_{j}$, and $h_{ij}=0$ otherwise. The Hermitian spectrum of a mixed graph is defined to be the spectrum of its Hermitian adjacency matrix. In this paper we study mixed graphs which are determined by their Hermitian spectrum (DHS). First, we show that each mixed cycle is switching equivalent to either a mixed cycle with no directed edges ($C_{n}$), a mixed cycle with exactly one directed edge ($C_{n}^{1}$), or a mixed cycle with exactly two consecutive directed edges with the same direction ($C_{n}^{2}$) and we determine the spectrum of these three types of cycles. Next, we characterize all DHS mixed paths and mixed cycles. We show that all mixed paths of even order, except $P_{8}$ and $P_{14}$, are DHS. It is also shown that mixed paths of odd order, except $P_{3}$, are not DHS. Also, all cospectral mates of $P_{8}$, $P_{14}$ and $P_{4k+1}$ and two families of cospectral mates of $P_{4k+3}$, where $k\geq1$, are introduced. Finally, we show that the mixed cycles $C_{2k}$ and $C_{2k}^{2}$, where $k\geq3$, are not DHS, but the mixed cycles $C_{4}$, $C_{4}^{2}$, $C_{2k+1}$, $C_{2k+1}^{2}$, $C_{2k+1}^{1}$ and $C_{2j}^{1}$ except $C_{7}^{1}$, $C_{9}^{1}$, $C_{12}^{1}$ and $C_{15}^{1}$, are DHS, where $k\geq1$ and $j\geq2$.
△ Less
Submitted 10 June, 2018;
originally announced June 2018.
-
Chromatic Number and Dichromatic Polynomial of Digraphs
Authors:
Saeed Akbari,
Amir Hossein Ghodrati,
Afrouz Jabalameli,
Morteza Saghafian
Abstract:
Let $G$ be a graph of order $n$. It is well-known that $α(G)\geq \sum_{i=1}^n \frac{1}{1+d_i}$, where $α(G)$ is the independence number of $G$ and $d_1,\ldots,d_n$ is the degree sequence of $G$. We extend this result to digraphs by showing that if $D$ is a digraph with $n$ vertices, then $ α(D)\geq \sum_{i=1}^n \left( \frac{1}{1+d_i^+} + \frac{1}{1+d_i^-}
- \frac{1}{1+d_i}\right)$, where $α(D)$…
▽ More
Let $G$ be a graph of order $n$. It is well-known that $α(G)\geq \sum_{i=1}^n \frac{1}{1+d_i}$, where $α(G)$ is the independence number of $G$ and $d_1,\ldots,d_n$ is the degree sequence of $G$. We extend this result to digraphs by showing that if $D$ is a digraph with $n$ vertices, then $ α(D)\geq \sum_{i=1}^n \left( \frac{1}{1+d_i^+} + \frac{1}{1+d_i^-}
- \frac{1}{1+d_i}\right)$, where $α(D)$ is the maximum size of an acyclic vertex set of $D$. Golowich proved that for any digraph $D$, $χ(D)\leq \lceil \frac{4k}{5} \rceil+2$, where $k=max(Δ^+(D),Δ^-(D))$. We give a short and simple proof for this result. Next, we investigate the chromatic number of tournaments and determine the unique tournament such that for every integer $k>1$, the number of proper $k$-colorings of that tournament is maximum among all strongly connected tournaments with the same number of vertices. Also, we find the chromatic polynomial of the strongly connected tournament with the minimum number of cycles.
△ Less
Submitted 16 November, 2017;
originally announced November 2017.
-
Signed graphs cospectral with the path
Authors:
Saieed Akbari,
Willem H. Haemers,
Hamid Reza Maimani,
Leila Parsaei Majd
Abstract:
A signed graph $Γ$ is said to be determined by its spectrum if every signed graph with the same spectrum as $Γ$ is switching isomorphic with $Γ$. 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$.
A signed graph $Γ$ is said to be determined by its spectrum if every signed graph with the same spectrum as $Γ$ is switching isomorphic with $Γ$. 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$.
△ Less
Submitted 10 May, 2018; v1 submitted 28 September, 2017;
originally announced September 2017.
-
Some Criteria for a Signed Graph to Have Full Rank
Authors:
S. Akbari,
A. Ghafari,
K. Kazemian,
M. Nahvi
Abstract:
A weighted graph $G^ω$ consists of a simple graph $G$ with a weight $ω$, which is a mapping,$ω$: $E(G)\rightarrow\mathbb{Z}\backslash\{0\}$. A signed graph is a graph whose edges are labeled with $-1$ or $1$. In this paper, we characterize graphs which have a sign such that their signed adjacency matrix has full rank, and graphs which have a weight such that their weighted adjacency matrix does no…
▽ More
A weighted graph $G^ω$ consists of a simple graph $G$ with a weight $ω$, which is a mapping,$ω$: $E(G)\rightarrow\mathbb{Z}\backslash\{0\}$. A signed graph is a graph whose edges are labeled with $-1$ or $1$. In this paper, we characterize graphs which have a sign such that their signed adjacency matrix has full rank, and graphs which have a weight such that their weighted adjacency matrix does not have full rank. We show that for any arbitrary simple graph $G$, there is a sign $σ$ so that $G^σ$ has full rank if and only if $G$ has a $\{1,2\}$-factor. We also show that for a graph $G$, there is a weight $ω$ so that $G^ω$ does not have full rank if and only if $G$ has at least two $\{1,2\}$-factors.
△ Less
Submitted 23 August, 2017;
originally announced August 2017.
-
Maximum nullity and zero forcing number on cubic graphs
Authors:
Saieed Akbari,
Ebrahim Vatandoost,
Yasser Golkhandy Pour
Abstract:
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…
▽ More
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$.
△ Less
Submitted 27 May, 2017;
originally announced May 2017.
-
Graphs with Integer Matching Polynomial Roots
Authors:
S. Akbari,
P. Csikvari,
A. Ghafari,
S. Khalashi Ghezelahmad,
M. Nahvi
Abstract:
In this paper, we study graphs whose matching polynomial have only integer zeros. A graph is matching integral if the zeros of its matching polynomial are all integers. We characterize all matching integral traceable graphs.. We show that apart from K7 n (E(C3) [ E(C4)) there is no connected k-regular matching integral graph if k ? 2. It is also shown that if G is a graph with a perfect matching,…
▽ More
In this paper, we study graphs whose matching polynomial have only integer zeros. A graph is matching integral if the zeros of its matching polynomial are all integers. We characterize all matching integral traceable graphs.. We show that apart from K7 n (E(C3) [ E(C4)) there is no connected k-regular matching integral graph if k ? 2. It is also shown that if G is a graph with a perfect matching, then its matching polynomial has a zero in the interval (0, 1]. Finally, we describe all claw-free matching integral graphs.
△ Less
Submitted 5 February, 2017; v1 submitted 2 August, 2016;
originally announced August 2016.
-
Hoffmann-Ostenhof's conjecture for traceable cubic graphs
Authors:
F. Abdolhosseini,
S. Akbari,
H. Hashemi,
M. S. Moradian
Abstract:
It was conjectured by Hoffmann-Ostenhof that the edge set of every connected cubic graph can be decomposed into a spanning tree, a matching and a family of cycles. In this paper, we show that this conjecture holds for traceable cubic graphs.
It was conjectured by Hoffmann-Ostenhof that the edge set of every connected cubic graph can be decomposed into a spanning tree, a matching and a family of cycles. In this paper, we show that this conjecture holds for traceable cubic graphs.
△ Less
Submitted 16 July, 2016;
originally announced July 2016.
-
Equimatchable Claw-Free Graphs
Authors:
Saieed Akbari,
Hadi Alizadeh,
Tınaz Ekim,
Didem Gözüpek,
Mordechai Shalom
Abstract:
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.
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.
△ Less
Submitted 24 July, 2018; v1 submitted 2 July, 2016;
originally announced July 2016.
-
On the structure of the power graph and the enhanced power graph of a group
Authors:
Ghodratollah Aalipour,
Saieed Akbari,
Peter J. Cameron,
Reza Nikandish,
Farzad Shaveisi
Abstract:
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…
▽ More
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.
△ Less
Submitted 14 March, 2016;
originally announced March 2016.
-
Improper Twin Edge Coloring of Graphs
Authors:
Paniz Abedin,
Saieed Akbari,
Marc Demange,
Tinaz Ekim
Abstract:
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…
▽ More
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 $χ'_{it}(G)$.
In this paper, we show that if $G$ is a graph with vertex chromatic number $χ(G)$, then $χ'_{it}(G)=χ(G)$, unless $χ(G)=2 \pmod 4$ and in this case $χ'_{it}(G)\in \{χ(G), χ(G)+1\}$. Moreover, we show that it is NP-hard to decide whether $χ'_{it}(G)=χ(G)$ or $χ'_{it}(G)=χ(G)+1$ and give some examples of perfect graph classes for which the problem is polynomial.
△ Less
Submitted 23 September, 2016; v1 submitted 10 January, 2016;
originally announced January 2016.
-
Cubic Graphs with Total Domatic Number at Least Two
Authors:
Saieed Akbari,
Mohammad Motiei,
Sahand Mozaffari,
Sina Yazdanbod
Abstract:
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.
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.
△ Less
Submitted 15 December, 2015;
originally announced December 2015.
-
On edge-decomposition of cubic graphs into copies of the double-star with four edges
Authors:
Saieed Akbari,
Hamidreza Maimani,
Abbas Seify
Abstract:
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…
▽ More
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 $α(G)= \frac{3n}{8}$ has an $S_{1,2}$-decomposition, where $α(G)$ denotes the independence number of $G$. Finally, we obtain some results on the $S_{1,r-1}$-decomposition of $r$-regular graphs.
△ Less
Submitted 10 September, 2015;
originally announced September 2015.
-
The Prime Index Graph of a Group
Authors:
S. Akbari,
A. Ashtab,
F. Heydari,
M. Rezaee,
F. Sherafati
Abstract:
Let $G$ be a group. The prime index graph of $G$, denoted by $Π(G)$, is the graph whose vertex set is the set of all subgroups of $G$ and two distinct comparable vertices $H$ and $K$ are adjacent if and only if the index of $H$ in $K$ or the index of $K$ in $H$ is prime. In this paper, it is shown that for every group $G$, $Π(G)$ is bipartite and the girth of $Π(G)$ is contained in the set…
▽ More
Let $G$ be a group. The prime index graph of $G$, denoted by $Π(G)$, is the graph whose vertex set is the set of all subgroups of $G$ and two distinct comparable vertices $H$ and $K$ are adjacent if and only if the index of $H$ in $K$ or the index of $K$ in $H$ is prime. In this paper, it is shown that for every group $G$, $Π(G)$ is bipartite and the girth of $Π(G)$ is contained in the set $\{4,\infty\}$. Also we prove that if $G$ is a finite solvable group, then $Π(G)$ is connected.
△ Less
Submitted 5 August, 2015;
originally announced August 2015.
-
Erratum to: Matching Subspaces in a Field Extension
Authors:
Saieed Akbari,
Mohsen Aliabadi
Abstract:
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.
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.
△ Less
Submitted 24 July, 2015;
originally announced July 2015.
-
Double-Star Decomposition of Regular Graphs
Authors:
Saieed Akbari,
Shahab Haghi,
Hamidreza Maimani,
Abbas Seify
Abstract:
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 sh…
▽ More
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$.
△ Less
Submitted 20 May, 2015;
originally announced May 2015.
-
On 1-sum flows in undirected graphs
Authors:
S. Akbari,
S. Friedland,
K. Markström,
S. Zare
Abstract:
Let G=(V,E) be a simple undirected graph. For a given set L of the real line, a function omega from E to L is called an L-flow. Given a vector gamma whose coordinates are indexed by V, we say that omega is a gamma-L-flow if for each v in V, the sum of the values on the edges incident to v is gamma(v). If gamma(v)=c, for all v in V, then the gamma-L-flow is called a c-sum L-flow. In this paper we s…
▽ More
Let G=(V,E) be a simple undirected graph. For a given set L of the real line, a function omega from E to L is called an L-flow. Given a vector gamma whose coordinates are indexed by V, we say that omega is a gamma-L-flow if for each v in V, the sum of the values on the edges incident to v is gamma(v). If gamma(v)=c, for all v in V, then the gamma-L-flow is called a c-sum L-flow. In this paper we study the existence of gamma-L-flows for various choices of sets L of real numbers, with an emphasis on 1-sum flows.
Given a natural k number, a c-sum k-flow is a c-sum flow with values from the set {-1,1,...,1-k, k-1}. Let L be a subset of real numbers containing 0 and let L* be L minus 0 by L*. Answering a question from a recent paper we characterize which bipartite graphs admit a 1-sum R*-flow or a 1-sum Z*-flow. We also show that that every k-regular graph, with k either odd or congruent to 2 modulo 4, admits a 1-sum {-1, 0, 1}-flow.
△ Less
Submitted 24 March, 2015;
originally announced March 2015.
-
Zero-sum flows for Steiner triple systems
Authors:
S. Akbari,
A. C. Burgess,
P. Danziger,
E. Mendelsohn
Abstract:
Given a $2$-$(v,k,λ)$ design, $\cal{S}=(X,\cal{B})$, a {\it zero-sum $n$-flow} of $\cal{S}$ is a map $f: \cal{B} \longrightarrow \{\pm 1, \ldots ,\pm (n-1)\}$ such that for any point $x\in X$, the sum of $f$ around all the blocks incident with $x$ is zero. It has been conjectured that every Steiner triple system, STS$(v)$, on $v$ points $(v>7)$ admits a zero-sum $3$-flow. We show that for every pa…
▽ More
Given a $2$-$(v,k,λ)$ design, $\cal{S}=(X,\cal{B})$, a {\it zero-sum $n$-flow} of $\cal{S}$ is a map $f: \cal{B} \longrightarrow \{\pm 1, \ldots ,\pm (n-1)\}$ such that for any point $x\in X$, the sum of $f$ around all the blocks incident with $x$ is zero. It has been conjectured that every Steiner triple system, STS$(v)$, on $v$ points $(v>7)$ admits a zero-sum $3$-flow. We show that for every pair $(v,λ)$, for which a triple system, TS$(v,λ)$ exists, there exists one which has a zero-sum $3$-flow, except when $(v,λ)\in\{(3,1), (4,2), (6,2), (7,1)\}$ and except possibly when $v \equiv 10\pmod{12}$ and $λ= 2$. We also give a $O(λ^2v^2)$ bound on $n$ and a recursive result which shows that every STS$(v)$ with a zero-sum $3$-flow can be embedded in an STS$(2v+1)$ with a zero-sum $3$-flow if $v\equiv 3 \pmod 4$, a zero-sum $4$-flow if $v\equiv 3 \pmod 6$ and with a zero-sum $5$-flow if $v\equiv 1 \pmod 4$.
△ Less
Submitted 12 May, 2015; v1 submitted 13 February, 2015;
originally announced February 2015.
-
The f-Chromatic Index of Claw-free Graphs Whose f-Core is 2-regular
Authors:
S. Akbari,
M. Chavooshi,
M. Ghanbari,
R. Manaviyat
Abstract:
Let $G$ be a graph and $f:V(G)\rightarrow \mathbb{N}$ be a function. An $f$-coloring of a graph $G$ is an edge coloring such that each color appears at each vertex $v\in V(G)$ at most $f (v)$ times. The minimum number of colors needed to $f$-color $G$ is called the $f$-chromatic index of $G$ and is denoted by $χ'_{f}(G)$. It was shown that for every graph $G$,…
▽ More
Let $G$ be a graph and $f:V(G)\rightarrow \mathbb{N}$ be a function. An $f$-coloring of a graph $G$ is an edge coloring such that each color appears at each vertex $v\in V(G)$ at most $f (v)$ times. The minimum number of colors needed to $f$-color $G$ is called the $f$-chromatic index of $G$ and is denoted by $χ'_{f}(G)$. It was shown that for every graph $G$, $Δ_{f}(G)\le χ'_{f}(G)\le Δ_{f}(G)+1$, where $Δ_{f}(G)=\max_{v\in V(G)} \lceil \frac{d_G(v)}{f(v)} \rceil$. A graph $G$ is said to be $f$-Class $1$ if $χ'_{f}(G)=Δ_{f}(G)$, and $f$-Class $2$, otherwise. Also, $G_{Δ_f}$ is the induced subgraph of $G$ on $\{v\in V(G):\,\frac{d_G(v)}{f(v)}=Δ_{f}(G)\}$. In this paper, we show that if $G$ is a connected graph with $Δ(G_{Δ_f})\leq 2$ and $G$ has an edge cut of size at most $Δ_f(G) -2$ which is a matching or a star, then $G$ is $f$-Class $1$. Also, we prove that if $G$ is a connected graph and every connected component of $G_{Δ_f}$ is a unicyclic graph or a tree and $G_{Δ_f}$ is not $2$-regular, then $G$ is $f$-Class $1$. Moreover, we show that except one graph, every connected claw-free graph $G$ whose $f$-core is $2$-regular with a vertex $v$ such that $f(v)\neq 1$ is $f$-Class $1$.
△ Less
Submitted 18 January, 2015;
originally announced January 2015.
-
A New Upper Bound on Total Domination Number of Bipartite Graphs
Authors:
Saieed Akbari,
Pooyan Ehsani,
Sahar Qajar,
Ali Shameli,
Hadi Yami
Abstract:
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, $γ_{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 $γ_{t}$($G$), whenever $G$ is a bipartite graph and $δ(G)$ $\geq$ $k$. More p…
▽ More
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, $γ_{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 $γ_{t}$($G$), whenever $G$ is a bipartite graph and $δ(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 $δ(G) \ge k$, $ $$γ_{t}$($G$) $\leq$ $n(1- \frac{k!}{\prod_{i=0}^{k-1}(\frac{k}{k-1}+i)}).$
△ Less
Submitted 28 December, 2014;
originally announced December 2014.
-
On the Decision Number of Graphs
Authors:
S. Akbari,
M. Dalirrooyfard,
S. Davodpoor,
K. Ehsani,
R. Sherkati
Abstract:
Let $G$ be a graph. A good function is a function $f:V(G)\rightarrow \{-1,1\}$, satisfying $f(N(v))\geq 1$, for each $v\in V(G)$, where $ N(v)=\{u\in V(G)\, |\, uv\in E(G) \} $ and $f(S) = \sum_{u\in S} f(u)$ for every $S \subseteq V(G) $. For every cubic graph $G$ of order $ n, $ we prove that $ γ(G) \leq \frac{5n}{7} $ and show that this inequality is sharp. A function…
▽ More
Let $G$ be a graph. A good function is a function $f:V(G)\rightarrow \{-1,1\}$, satisfying $f(N(v))\geq 1$, for each $v\in V(G)$, where $ N(v)=\{u\in V(G)\, |\, uv\in E(G) \} $ and $f(S) = \sum_{u\in S} f(u)$ for every $S \subseteq V(G) $. For every cubic graph $G$ of order $ n, $ we prove that $ γ(G) \leq \frac{5n}{7} $ and show that this inequality is sharp. A function $f:V(G)\rightarrow \{-1,1\}$ is called a nice function, if $f(N[v])\le1$, for each $v\in V(G)$, where $ N[v]=\{v\} \cup N(v) $. Define $\overlineβ(G)=max\{f(V(G))\}$, where $f$ is a nice function for $G$. We show that $\overlineβ(G)\ge -\frac{3n}{7}$ for every cubic graph $G$ of order $n$, which improves the best known bound $-\frac{n}{2}$.
△ Less
Submitted 11 June, 2014; v1 submitted 1 February, 2014;
originally announced February 2014.
-
Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges
Authors:
M. Aaghabali,
S. Akbari,
S. Friedland,
K. Markstrom,
Z. Tajfirouz
Abstract:
We give an upper bound on the number of perfect matchings in simple graphs with a given number of vertices and edges. We apply this result to give an upper bound on the number of 2-factors in a directed complete bipartite balanced graph on 2n vertices. The upper bound is sharp for n even. For n odd we state a conjecture on a sharp upper bound.
We give an upper bound on the number of perfect matchings in simple graphs with a given number of vertices and edges. We apply this result to give an upper bound on the number of 2-factors in a directed complete bipartite balanced graph on 2n vertices. The upper bound is sharp for n even. For n odd we state a conjecture on a sharp upper bound.
△ Less
Submitted 31 July, 2014; v1 submitted 21 October, 2013;
originally announced October 2013.
-
A Note on Co-Maximal Ideal Graph of Commutative Rings
Authors:
Saieed Akbari,
Babak Miraftab,
Reza Nikandish
Abstract:
Let $R$ be a commutative ring with unity. The co-maximal ideal graph of $R$, denoted by $Γ(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 pose…
▽ More
Let $R$ be a commutative ring with unity. The co-maximal ideal graph of $R$, denoted by $Γ(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 $Γ(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.
△ Less
Submitted 26 October, 2015; v1 submitted 20 July, 2013;
originally announced July 2013.
-
Application of some combinatorial arrays in coloring of total graph of a commutative ring
Authors:
Ghodratollah Aalipour,
Saieed Akbari
Abstract:
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(Γ(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(Γ(R))$ and…
▽ More
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(Γ(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(Γ(R))$ and $Reg(Γ(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(Γ(R))$ are equal to $\max\{|\mathfrak{m}|\,:\, \mathfrak{m}\in {\rm Max}(R)\}$. The same result holds for $Z(Γ(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(Γ(R))$ as well.
△ Less
Submitted 18 May, 2013;
originally announced May 2013.
-
On the Cayley graph of a commutative ring with respect to its zero-divisors
Authors:
Ghodratollah Aalipour,
Saieed Akbari
Abstract:
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.…
▽ More
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.
△ Less
Submitted 2 May, 2013;
originally announced May 2013.
