Source author record

Bahman Ahmadi

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

ResearcherUnclaimed source record

math.CO math.SP

Catalog footprint

Research overview

7works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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

preprint2022arXiv

Distinguishing threshold of graphs

A vertex coloring of a graph $G$ is called distinguishing if no non-identity automorphisms of $G$ can preserve it. The distinguishing number of $G$ , denoted by $D(G)$ , is the minimum number of colors required for such a coloring, and the distinguishing threshold of $G$ , denoted by $θ(G)$ , is the minimum number $k$ such that every $k$ -coloring of $G$ is distinguishing. As an alternative definition, $θ(G)$ is one more than the maximum number of cycles in the cycle decomposition of automorphisms of $G$ . In this paper, we characterize $θ(G)$ when $G$ is disconnected. Afterwards, we prove that, although for every positive integer $k\neq 2$ there are infinitely many graphs whose distinguishing thresholds are equal to $k$ , we have $θ(G)=2$ if and only if $\vert V(G)\vert =2$ . Moreover, we show that if $θ(G)=3$ , then either $G$ is isomorphic to one of the four graphs on~3 vertices or it is of order $2p$ , where $p\neq 3,5$ is a prime number. Furthermore, we prove that $θ(G)=D(G)$ if and only if $G$ is asymmetric, $K_n$ or $\overline{K_n}$ . Finally, we consider all generalized Johnson graphs, $J(n,k,i)$ , which are the graphs on all $k$ -subsets of $\{1,\ldots , n\}$ where two vertices $A$ and $B$ are adjacent if $|A\cap B|=k-i$ . After studying their automorphism groups and distinguishing numbers, we calculate their distinguishing thresholds as $θ(J(n,k,i))={n\choose k} - {n-2\choose k-1}+1$ , unless $k=\frac{n}{2}$ and $i\in\{ \frac{k}{2} , k\}$ in which case we have $θ(J(n,k,i))={n\choose k}$ .

preprint2013arXiv

A new proof for the Erdős-Ko-Rado Theorem for the alternating group

A subset $S$ of the alternating group on $n$ points is {\it intersecting} if for any pair of permutations $π,σ$ in $S$ , there is an element $i\in \{1,\dots,n\}$ such that $π(i)=σ(i)$ . We prove that if $S$ is intersecting, then $|S|\leq \frac{(n-1)!}{2}$ . Also, we prove that if $n \geq 5$ , then the only sets $S$ that meet this bound are the cosets of the stabilizer of a point of $\{1,\dots,n\}$ .

preprint2013arXiv

Maximum Intersecting Families of Permutations

It was first shown by Cameron and Ku that the group $G=Sym(n)$ has the strict EKR property. Then Godsil and Meagher presented an entirely different proof of this fact using some algebraic properties of the symmetric group. A similar method was employed to prove that the projective general linear group $PGL(2,q)$ , with its natural action on the projective line $\mathbb{P}_q$ , has the strict EKR property. The main objective in this thesis is to formally introduce this method, which we call the module method, and show that this provides a standard way to prove Erdos-Ko-Rado theorems for other permutation groups. We then, along with proving Erdos-Ko-Rado theorems for various groups, use this method to prove some permutation groups have the strict EKR property. We will also show that this method can be useful in characterizing the maximum independent sets of some Cayley graphs. To explain the module method, we need some facts from representation theory of groups, in particular, the symmetric group. We will provide the reader with a sufficient level of background from representation theory as well as graph theory and linear algebraic facts about graphs.

preprint2013arXiv

The Erdős-Ko-Rado property for some 2-transitive groups

A subset of a group G of Sym(n) is intersecting if for any pair of permutations $π,σ\in G$ there is an $i$ in {1,2,...,n} such that $π(i) = σ(i)$ . It has been shown, using an algebraic approach, that the largest intersecting sets in each of Sym(n), Alt(n) and PGL(2,q) are exactly the cosets of the point-stabilizers. In this paper, we show how this method can be applied more generally to many 2-transitive groups. We then apply this method to the Mathieu groups and to all 2-transtive groups with degree no more than 20.

preprint2013arXiv

The Erdős-Ko-Rado property for some permutation groups

A subset in a group $G \leq Sym(n)$ is intersecting if for any pair of permutations $π,σ$ in the subset there is an $i \in \{1,2,\dots,n\}$ such that $π(i) = σ(i)$ . If the stabilizer of a point is the largest intersecting set in a group, we say that the group has the Erdős-Ko-Rado (EKR) property. Moreover, the group has the strict EKR property if every intersecting set of maximum size in the group is either the stabilizer of a point or the coset of the stabilizer of a point. In this paper we look at several families of permutation groups and determine if the groups have either the EKR property or the strict EKR property. First, we prove that all cyclic groups have the strict EKR property. Next we show that all dihedral and Frobenius groups have the EKR property and we characterize which ones have the strict EKR property. Further, we show that if all the groups in an external direct sum or an internal direct sum have the EKR (or strict EKR) property, then the product does as well. Finally, we show that the wreath product of two groups with EKR property also has the EKR property.

preprint2011arXiv

The minimum rank of universal adjacency matrices

In this paper we introduce a new parameter for a graph called the {\it minimum universal rank}. This parameter is similar to the minimum rank of a graph. For a graph $G$ the minimum universal rank of $G$ is the minimum rank over all matrices of the form $U(α, β, γ, δ) = αA + βI + γJ + δD$ where $A$ is the adjacency matrix of $G$ , $J$ is the all ones matrix and $D$ is the matrix with the degrees of the vertices in the main diagonal, and $α\neq 0, β, γ, δ$ are scalars. Bounds for general graphs based on known graph parameters are given, as is a formula for the minimum universal rank for regular graphs based on the multiplicity of the eigenvalues of $A$ . The exact value of the minimum universal rank of some families of graphs are determined, including complete graphs, complete bipartite graph, paths and cycles. Bounds on the minimum universal rank of a graph obtained by deleting a single vertex are established. It is shown that the minimum universal rank is not monotone on induced subgraphs, but bounds based on certain induced subgraphs, including bounds on the union of two graphs, are given. Finally we characterize all graphs with minimum universal rank equal to 0 and to 1.

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.

Bahman Ahmadi

Research overview

Is this your work?

7 publications

Distinguishing threshold for some graph operations

Distinguishing threshold of graphs

A new proof for the Erdős-Ko-Rado Theorem for the alternating group

Maximum Intersecting Families of Permutations

The Erdős-Ko-Rado property for some 2-transitive groups

The Erdős-Ko-Rado property for some permutation groups

The minimum rank of universal adjacency matrices

See the researcher in context

Building this map preview