Source author record

Saieed Akbari

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.AC

Catalog footprint

Research overview

16works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

On Prime Matrix Product Factorizations

A graph $G$ factors into graphs $H$ and $K$ via a matrix product if $A = BC$ , where $A$ , $B$ , and $C$ are the adjacency matrices of $G$ , $H$ , and $K$ , respectively. The graph $G$ is prime if, in every such factorization, one of the factors is a perfect matching that is, it corresponds to a permutation matrix. We characterize all prime graphs, then using this result we classify all factorable forests, answering a question of Akbari et al. [\emph{Linear Algebra and its Applications} (2025)]. We prove that every torus is factorable, and we characterize all possible factorizations of grids, addressing two questions posed by Maghsoudi et al. [\emph{Journal of Algebraic Combinatorics} (2025)].

preprint2022arXiv

A lower bound of the energy of non-singular graphs in terms of average degree

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$

preprint2021arXiv

On a question of Haemers regarding vectors in the nullspace of Seidel matrices

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.

preprint2021arXiv

Zero-sum flows for Steiner systems

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.

preprint2020arXiv

Decomposing 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.

preprint2016arXiv

Improper Twin Edge Coloring of Graphs

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.

preprint2015arXiv

A Note on Co-Maximal Ideal Graph of Commutative Rings

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.

preprint2015arXiv

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.

preprint2015arXiv

Double-Star Decomposition of Regular Graphs

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$ .

preprint2015arXiv

Erratum to: Matching Subspaces in a Field Extension

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.

preprint2015arXiv

Even and Odd Cycles Passing a Given Edge or a Vertex

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

preprint2015arXiv

On edge-decomposition of cubic graphs into copies of the double-star with four edges

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.

preprint2014arXiv

A New Upper Bound on Total Domination Number of Bipartite Graphs

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)}).$

preprint2013arXiv

Application of some combinatorial arrays in coloring of total graph of a commutative ring

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.

preprint2013arXiv

On the Cayley graph of a commutative ring with respect to its zero-divisors

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.

preprint2012arXiv

Harmonious Coloring of Trees with Large Maximum Degree

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

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Saieed Akbari

Research overview

Is this your work?

16 publications

On Prime Matrix Product Factorizations

A lower bound of the energy of non-singular graphs in terms of average degree

On a question of Haemers regarding vectors in the nullspace of Seidel matrices

Zero-sum flows for Steiner systems

Decomposing Claw-free Subcubic Graphs and $4$ -Chordal Subcubic Graphs

Improper Twin Edge Coloring of Graphs

A Note on Co-Maximal Ideal Graph of Commutative Rings

Cubic Graphs with Total Domatic Number at Least Two

Double-Star Decomposition of Regular Graphs

Erratum to: Matching Subspaces in a Field Extension

Even and Odd Cycles Passing a Given Edge or a Vertex

On edge-decomposition of cubic graphs into copies of the double-star with four edges

A New Upper Bound on Total Domination Number of Bipartite Graphs

Application of some combinatorial arrays in coloring of total graph of a commutative ring

On the Cayley graph of a commutative ring with respect to its zero-divisors

Harmonious Coloring of Trees with Large Maximum Degree

See the researcher in context

Building this map preview

Saieed Akbari

Research overview

Is this your work?

16 publications

On Prime Matrix Product Factorizations

A lower bound of the energy of non-singular graphs in terms of average degree

On a question of Haemers regarding vectors in the nullspace of Seidel matrices

Zero-sum flows for Steiner systems

Decomposing Claw-free Subcubic Graphs and 444-Chordal Subcubic Graphs

Improper Twin Edge Coloring of Graphs

A Note on Co-Maximal Ideal Graph of Commutative Rings

Cubic Graphs with Total Domatic Number at Least Two

Double-Star Decomposition of Regular Graphs

Erratum to: Matching Subspaces in a Field Extension

Even and Odd Cycles Passing a Given Edge or a Vertex

On edge-decomposition of cubic graphs into copies of the double-star with four edges

A New Upper Bound on Total Domination Number of Bipartite Graphs

Application of some combinatorial arrays in coloring of total graph of a commutative ring

On the Cayley graph of a commutative ring with respect to its zero-divisors

Harmonious Coloring of Trees with Large Maximum Degree

See the researcher in context

Building this map preview

Decomposing Claw-free Subcubic Graphs and $4$ -Chordal Subcubic Graphs