Hiranya Kishore Dey

Search for another author

Author Description

Ask a Question About This Mathematician

All published works (45)

On the domination number of proper power graphs of finite groups

2025-05-09

Sudip Bera , Hiranya Kishore Dey , Kamal Lochan Patra +1 more

An exact enumeration of vertex connectivity of the enhanced power graphs of finite nilpotent groups

2025-05-01

Sudip Bera , Hiranya Kishore Dey

Enumerating alternating-runs with sign in Type A and Type B Coxeter groups

2025-02-13

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

A descent-excedance correspondence in colored permutation groups

2024-10-30

Hiranya Kishore Dey , Umesh Shankar , Sivaramakrishnan Sivasubramanian

It is well known that descents and excedances are equidistributed in the symmetric group. We show that the descent and excedance enumerators, summed over permutations with a fixed first letter … It is well known that descents and excedances are equidistributed in the symmetric group. We show that the descent and excedance enumerators, summed over permutations with a fixed first letter are identical when we perform a simple change of the first letter. We generalize this to type B and other colored permutation groups. We are led to defining descents and excedances through linear orders. With respect to a particular order, when the number of colors is even, we get a result that generalizes the type B results. Lastly, we get a type B counterpart of Conger's result which refines the well known Carlitz identity.

Chat View PDF

Sign-balance of excedances over mod-k-alternating permutations and gamma-positivity

2024-07-31

Hiranya Kishore Dey , Iswar Mahato

A permutation is called mod-k-alternating if its entries are restricted to having the same remainder as the index, modulo some integer $k \geq 1.$ In this paper, we find the … A permutation is called mod-k-alternating if its entries are restricted to having the same remainder as the index, modulo some integer $k \geq 1.$ In this paper, we find the sign-balance for mod-k-alternating permutations with respect to the statistic excedance. Moreover, we study the sign-balance for excedances over mod-k-alternating derangements. The results are obtained by constructing suitable matrices and connecting their determinants with the signed excedance enumeration of mod-k-alternating permutations. As an application of the signed excedance enumeration, we prove that when $n \equiv k \pmod {2k}$, the excedance enumerating polynomials over the even and odd mod-k-alternating permutations, starting with a fixed remainder, are gamma-positive.

Chat View PDF

On the difference of the enhanced power graph and the power graph of a finite group

2024-06-21

Sucharita Biswas , Peter J‎. Cameron , Angsuman Das +1 more

Chat View PDF

How large is the character degree sum compared to the character table sum for a finite group?

2024-06-10

Arvind Ayyer , Hiranya Kishore Dey , Digjoy Paul

In 1961, Solomon gave upper and lower bounds for the sum of all the entries in the character table of a finite group in terms of elementary properties of the … In 1961, Solomon gave upper and lower bounds for the sum of all the entries in the character table of a finite group in terms of elementary properties of the group. In a different direction, we consider the ratio of the character table sum to the sum of the entries in the first column, also known as the character degree sum, in this work. First, we propose that this ratio is at most two for many natural groups. Secondly, we extend a conjecture of Fields to postulate that this ratio is at least one with equality if and only if the group is abelian. We establish the validity of this property and conjecture for all finite irreducible Coxeter groups. In addition, we prove the conjecture for generalized symmetric groups. The main tool we use is that the sum of a column in the character table of an irreducible Coxeter group (resp. generalized symmetric group) is given by the number of square roots (resp. absolute square roots) of the corresponding conjugacy class representative. As a byproduct of our results, we show that the asymptotics of character table sums is the same as the number of involutions in symmetric, hyperoctahedral and demihyperoctahedral groups. We also derive explicit generating functions for the character table sums for these latter groups as infinite products of continued fractions. In the same spirit, we prove similar generating function formulas for the number of square roots and absolute square roots in $n$ for the generalized symmetric groups $G(r,1,n)$.

Chat View PDF

An exact enumeration of vertex connectivity of the enhanced power graphs of finite nilpotent groups

2024-05-02

Sudip Bera , Hiranya Kishore Dey

The enhanced power graph of a group $G$ is a graph with vertex set $G,$ where two distinct vertices $x$ and $y$ are adjacent if and only if there exists … The enhanced power graph of a group $G$ is a graph with vertex set $G,$ where two distinct vertices $x$ and $y$ are adjacent if and only if there exists an element $w$ in $G$ such that both $x$ and $y$ are powers of $w.$ In this paper, we determine the vertex connectivity of the enhanced power graph of any finite nilpotent group.

Chat View PDF

An exact upper bound for the sum of powers of element orders in non-cyclic finite groups

2023-12-07

Hiranya Kishore Dey , Archita Mondal

Chat View PDF

q-Enumeration of type B and type D Eulerian polynomials based on parity of descents

2023-06-16

Hiranya Kishore Dey , Umesh Shankar , Sivaramakrishnan Sivasubramanian

Carlitz and Scoville in 1973 considered a four-variable polynomial that enumerates permutations in S n with respect to the parity of its descents and ascents.In recent work, Pan and Zeng … Carlitz and Scoville in 1973 considered a four-variable polynomial that enumerates permutations in S n with respect to the parity of its descents and ascents.In recent work, Pan and Zeng proved a q-analogue of Carlitz-Scoville's generating function by enumerating permutations with the above four statistics along with the inversion number.Further, they also proved a type B analogue by enumerating signed permutations with respect to the parity of descents and ascents.In this work, we prove a q-analogue of the type B result of Pan and Zeng by enumerating permutations in B n with the above four statistics and the type B inversion number.We also obtain a q-analogue of the generating function for the type B bivariate alternating descent polynomials.We consider a similar five-variable polynomial in the type D Coxeter groups as well and give their egf.Alternating descents for the type D groups were previously also defined by Remmel, but our definition is slightly different.As a by-product of our proofs, we get bivariate q-analogues of Hyatt's recurrences for the type B and type D Eulerian polynomials.Further corollaries of our results are some symmetry relations for these polynomials and q-analogues of generating functions for snakes of types B and D.

Signed alternating descent enumeration in classical Weyl groups

2023-06-08

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

Interlacing of zeroes of certain real-rooted polynomials

2023-02-14

Hiranya Kishore Dey

Sharp lower bound on the "number of nodal decomposition" of graphs

2023-01-01

Hiranya Kishore Dey , Soumyajit Saha

Urschel introduced a notion of nodal partitioning to prove an upper bound on the number of nodal decomposition of discrete Laplacian eigenvectors. The result is an analogue to the well-known … Urschel introduced a notion of nodal partitioning to prove an upper bound on the number of nodal decomposition of discrete Laplacian eigenvectors. The result is an analogue to the well-known Courant's nodal domain theorem on continuous Laplacian. In this article, using the same notion of partitioning, we discuss the lower bound (or lack thereof) on the number of nodal decomposition of eigenvectors in the class of all graphs with a fixed number of vertices (however large). This can be treated as a discrete analogue to the results of Stern and Lewy in the continuous Laplacian case.

Chat View PDF

Distance matrix of enhanced power graphs of finite groups

2023-01-01

Anita Arora , Hiranya Kishore Dey , Shivani Goel

The enhanced power graph of a group $G$ is the graph $\mathcal{G}_E(G)$ with vertex set $G$ and edge set $ \{(u,v): u, v \in \langle w \rangle,~\mbox{for some}~ w \in … The enhanced power graph of a group $G$ is the graph $\mathcal{G}_E(G)$ with vertex set $G$ and edge set $ \{(u,v): u, v \in \langle w \rangle,~\mbox{for some}~ w \in G\}$. In this paper, we compute the spectrum of the distance matrix of the enhanced power graph of non-abelian groups of order $pq$, dihedral groups, dicyclic groups, elementary abelian groups $\mathrm{El}(p^n)$ and the non-cyclic abelian groups $\mathrm{El}(p^n)\times\mathrm{El}(q^m)$ and $\mathrm{El}(p^n)\times \mathbb{Z}_m$, where $p$ and $q$ are distinct primes. For the non-cyclic abelian group $\mathrm{El}(p^n)\times \mathrm{El}(q^m)$, we also compute the spectrum of the adjacency matrix of its enhanced power graph and the spectrum of the adjacency and the distance matrix of its power graph.

Chat View PDF

On the order sequence of a group

2023-01-01

Peter J‎. Cameron , Hiranya Kishore Dey

This paper provides a bridge between two active areas of research, the spectrum (set of element orders) and the power graph of a finite group. The order sequence of a … This paper provides a bridge between two active areas of research, the spectrum (set of element orders) and the power graph of a finite group. The order sequence of a finite group $G$ is the list of orders of elements of the group, arranged in non-decreasing order. Order sequences of groups of order $n$ are ordered by elementwise domination, forming a partially ordered set. We prove a number of results about this poset, among them the following. M.~Amiri recently proved that the poset has a unique maximal element, corresponding to the cyclic group. We show that the product of orders in a cyclic group of order $n$ is at least $q^{\phi(n)}$ times as large as the product in any non-cyclic group,where $q$ is the smallest prime divisor of $n$ and $\phi$ is Euler's function, with a similar result for the sum. The poset of order sequences of abelian groups of order $p^n$ is naturally isomorphic to the (well-studied) poset of partitions of $n$ with its natural partial order. If there exists a non-nilpotent group of order $n$, then there exists such a group whose order sequence is dominated by the order sequence of any nilpotent group of order $n$. There is a product operation on finite ordered sequences, defined by forming all products and sorting them into non-decreasing order. The product of order sequences of groups $G$ and $H$ is the order sequence of a group if and only if $|G|$ and $|H|$ are coprime. The paper concludes with a number of open problems.

Chat View PDF

On some properties of vector space based graphs

2022-09-13

Peter J‎. Cameron , Angsuman Das , Hiranya Kishore Dey

In this paper, we study some problems related to subspace inclusion graph In⁡(V) and subspace sum graph G(V) of a finite-dimensional vector space V. Namely, we prove that In⁡(V) is … In this paper, we study some problems related to subspace inclusion graph In⁡(V) and subspace sum graph G(V) of a finite-dimensional vector space V. Namely, we prove that In⁡(V) is a Cayley graph as well as Hamiltonian when the dimension of V is 3. We also find the exact value of independence number of G(V) when the dimension of V is odd. The above two problems were left open in previous works in the literature. Moreover, we prove that the determining numbers of In⁡(V) and G(V) are bounded above by 6. Finally, we study some forbidden subgraphs of these two graphs.

Chat View PDF

On the proper enhanced power graphs of finite nilpotent groups

2022-07-13

Sudip Bera , Hiranya Kishore Dey

Abstract For a group 𝐺, the enhanced power graph of 𝐺 is a graph with vertex set 𝐺 in which two distinct vertices <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>x</m:mi> <m:mo>,</m:mo> <m:mi>y</m:mi> </m:mrow> … Abstract For a group 𝐺, the enhanced power graph of 𝐺 is a graph with vertex set 𝐺 in which two distinct vertices <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>x</m:mi> <m:mo>,</m:mo> <m:mi>y</m:mi> </m:mrow> </m:math> x,y are adjacent if and only if there exists an element 𝑤 in 𝐺 such that both 𝑥 and 𝑦 are powers of 𝑤. The proper enhanced power graph is the induced subgraph of the enhanced power graph on the set <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>G</m:mi> <m:mo>∖</m:mo> <m:mi>S</m:mi> </m:mrow> </m:math> G\setminus S , where 𝑆 is the set of dominating vertices of the enhanced power graph. In this paper, we at first classify all nilpotent groups 𝐺 such that the proper enhanced power graphs are connected and calculate their diameter. We also explicitly calculate the domination number of the proper enhanced power graphs of finite nilpotent groups. Finally, we determine the multiplicity of the Laplacian spectral radius of the enhanced power graphs of nilpotent groups.

Determining Number of Kneser Graphs: Exact Values and Improved Bounds

2022-03-30

Angsuman Das , Hiranya Kishore Dey

The determining number of a graph $G = (V,E)$ is the minimum cardinality of a set $S\subseteq V$ such that pointwise stabilizer of $S$ under the action of $Aut(G)$ is … The determining number of a graph $G = (V,E)$ is the minimum cardinality of a set $S\subseteq V$ such that pointwise stabilizer of $S$ under the action of $Aut(G)$ is trivial. In this paper, we provide some improved upper and lower bounds on the determining number of Kneser graphs. Moreover, we provide the exact value of the determining number for some subfamilies of Kneser graphs.

Chat View PDF

Eulerian central limit theorems and Carlitz identities in positive elements of classical Weyl groups

2022-01-01

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

Central Limit Theorems are known for the Eulerian statistic descent (or excedance) in the symmetric group $\SSS_n$. Recently, Fulman, Kim, Lee and Petersen gave a Central Limit Theorem for descent … Central Limit Theorems are known for the Eulerian statistic descent (or excedance) in the symmetric group $\SSS_n$. Recently, Fulman, Kim, Lee and Petersen gave a Central Limit Theorem for descent over the alternating group $\AAA_n$ and also gave a Carlitz identity in $\AAA_n$ using descents. In this paper, we give a Central Limit Theorem in $\AAA_n$ involving excedances. We extend these to the positive elements in type B and type D Coxeter groups. Boroweic and Mlotkowski enumerated type B descents over $\DD_n$, the type D Coxeter group and gave similar results. We refine their results for both the positive and negative part of $\DD_n$. Our results are a consequence of signed enumeration over these subsets.

Chat View PDF

On Difference of Enhanced Power Graph and Power Graph of a Finite Group

2022-01-01

Sucharita Biswas , Peter J‎. Cameron , Angsuman Das +1 more

The difference graph $D(G)$ of a finite group $G$ is the difference of enhanced power graph of $G$ and power graph of $G$, with all isolated vertices are removed. In … The difference graph $D(G)$ of a finite group $G$ is the difference of enhanced power graph of $G$ and power graph of $G$, with all isolated vertices are removed. In this paper we study the connectedness and perfectness of $D(G)$ with respect to various properties of the underlying group $G$. We also find several connection between the difference graph of $G$ and the Gruenberg-Kegel graph of $G$.

Chat View PDF

An exact upper bound for the sum of powers of element orders in non-cyclic finite groups

2022-01-01

Hiranya Kishore Dey , Archita Mondal

For a finite group $G$, let $\psi(G)$ denote the sum of element orders of $G$. This function was introduced by Amiri, Amiri, and Isaacs in 2009 and they proved that … For a finite group $G$, let $\psi(G)$ denote the sum of element orders of $G$. This function was introduced by Amiri, Amiri, and Isaacs in 2009 and they proved that for any finite group $G$ of order $n$, $\psi(G)$ is maximum if and only if $G \simeq \mathbb{Z}_n$ where $\mathbb{Z}_n$ denotes the cyclic group of order $n$. Furthermore, Herzog, Longobardi, and Maj in 2018 proved that if $G$ is non-cyclic, $\psi(G) \leq \frac{7}{11} \psi(\mathbb{Z}_n)$. Amiri and Amiri in 2014 introduced the function $\psi_k(G)$ which is defined as the sum of the $k$-th powers of element orders of $G$ and they showed that for every positive integer $k$, $\psi_k(G)$ is also maximum if and only if $G$ is cyclic. In this paper, we have been able to prove that if $G$ is a non-cyclic group of order $n$, then $\psi_k(G) \leq \frac{1+3.2^k}{1+2.4^k+2^k} \psi_k(\mathbb{Z}_n)$. Setting $k=1$ in our result, we immediately get the result of Herzog et al. as a simple corollary. Besides, a recursive formula for $\psi_k(G)$ is also obtained for finite abelian $p$-groups $G$, using which one can explicitly find out the exact value of $\psi_k(G)$ for finite abelian groups $G$.

Chat View PDF

$q$-enumeration of type B and D Eulerian polynomials based on parity of descents

2022-01-01

Hiranya Kishore Dey , Umesh Shankar , Sivaramakrishnan Sivasubramanian

Carlitz and Scoville in 1973 considered a four variable polynomial that enumerates permutations in $\mathfrak{S}_n$ with respect to the parity of its descents and ascents. In recent work, Pan and … Carlitz and Scoville in 1973 considered a four variable polynomial that enumerates permutations in $\mathfrak{S}_n$ with respect to the parity of its descents and ascents. In recent work, Pan and Zeng proved a $q$-analogue of Carlitz-Scoville's generating function by enumerating permutations with the above four statistice along with the inversion number. Further, they also proved a type B analogue by enumerating signed permutations with respect to the parity of descents and ascents. In this work we prove a $q$-analogue of the type B result of Pan and Zeng by enumerating permutations in $\mathfrak{B}_n$ with the above four statistics and the type B inversion number. We also obtain a $q$-analogue of the generating function for the type B bivariate alternating descent polynomials. We consider a similar five-variable polynomial in the type D Coxeter groups as well and give their egf. Alternating descents for the type D groups were previously also defined by Remmel, but our definition is slightly different. As a by-product of our proofs, we get bivariate $q$-analogues of Hyatt's recurrences for the type B and type D Eulerian polynomials. Further corollaries of our results are some symmetry relations for these polynomials and $q$-analogues of generating functions for snakes of types B and D.

Chat View PDF

The solvability of a finite group by the sum of powers of element orders

2022-01-01

Hiranya Kishore Dey

We prove a new criterion for the solvability of the finite groups, depending on the function $\psi_k(G)$ which is defined as the sum of $k$-th powers of the element orders … We prove a new criterion for the solvability of the finite groups, depending on the function $\psi_k(G)$ which is defined as the sum of $k$-th powers of the element orders of $G$. We show that our result can be used to show the solvability of some groups for which the solvability does not follow from earlier similar kind of results and we emphasize the following: looking at $\psi_k(G)$ for $k>1$ can be useful to get further pieces of information about the group $G$.

Chat View PDF

On connectivity, domination number and spectral radius of the proper enhanced power graphs of finite nilpotent groups

2021-08-11

Sudip Bera , Hiranya Kishore Dey

For a group $G,$ the enhanced power graph of $G$ is a graph with vertex set $G$ in which two distinct elements $x, y$ are adjacent if and only if … For a group $G,$ the enhanced power graph of $G$ is a graph with vertex set $G$ in which two distinct elements $x, y$ are adjacent if and only if there exists an element $w$ in $G$ such that both $x$ and $y$ are powers of $w.$ The proper enhanced power graph is the induced subgraph of the enhanced power graph on the set $G \setminus S,$ where $S$ is the set of dominating vertices of the enhanced power graph. In this paper, we first characterize the dominating vertices of enhanced power graph of any finite nilpotent group. Thereafter, we classify all nilpotent groups $G$ such that the proper enhanced power graphs are connected and find out their diameter. We also explicitly find out the domination number of proper enhanced power graphs of finite nilpotent groups. Finally, we determine the multiplicity of the Laplacian spectral radius of the enhanced power graphs of nilpotent groups.

Chat View PDF

Log-concavity of the excedance enumerators in positive elements of Type A and Type B Coxeter Groups

2021-04-05

Hiranya Kishore Dey

Chat View PDF

On the Connectivity of Enhanced Power Graphs of Finite Groups

2021-01-03

Sudip Bera , Hiranya Kishore Dey , Sajal Kumar Mukherjee

The Young matroid: A multiset extension of the Catalan matroid to arbitrary Young diagrams

2021-01-01

Hiranya Kishore Dey , Brahadeesh Sankarnarayanan , S. Venkitesh

Introduced by Ardila (J. Combin. Theory Ser. A, 2003), the Catalan matroid is obtained by defining the bases of the matroid using Dyck paths from $(0,0)$ to $(n,n)$. Further research … Introduced by Ardila (J. Combin. Theory Ser. A, 2003), the Catalan matroid is obtained by defining the bases of the matroid using Dyck paths from $(0,0)$ to $(n,n)$. Further research has gone into the topic, with variants like lattice path matroids (introduced by Bonin, de Mier, and Noy (J. Combin. Theory Ser. A, 2003)) and shifted matroids (introduced independently by Klivans (2003), and Ardila) being studied intensively. In this short note, we introduce the Young matroid, an extension of the Catalan matroid, where the bases are defined using the standard Young tableaux of a fixed shape. This extension necessarily involves the consideration of independent multisets and multiset bases.

Chat View PDF

On connectivity, domination number and spectral radius of the proper enhanced power graphs of finite nilpotent groups

2021-01-01

Sudip Bera , Hiranya Kishore Dey

Chat View PDF

Combinatorial proof of the log-convexity for the derangements in the Coxeter groups.

2020-11-18

Hiranya Kishore Dey , Subhajit Ghosh

We provide the combinatorial proofs of the log-convexity for the derangement numbers in the symmetric group $\mathfrak{S}_n$, hyperoctahedral group $\mathfrak{B}_n$, and the demihyperoctahedral group $\mathfrak{D}_n$. We also show that the … We provide the combinatorial proofs of the log-convexity for the derangement numbers in the symmetric group $\mathfrak{S}_n$, hyperoctahedral group $\mathfrak{B}_n$, and the demihyperoctahedral group $\mathfrak{D}_n$. We also show that the sequences of the even and odd derangement numbers in $\mathfrak{S}_n$ and $\mathfrak{B}_n$ are log-convex.

Chat View PDF

Signed Alternating-runs enumeration in Classical Weyl Groups.

2020-10-19

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

The alternating-runs polynomial enumerates alternating runs in the symmetric group. There are three formulae for the number of permutations, $R_{n,k}$ in $\mathfrak{S}_n$ with $k$ alternating runs, but all of them … The alternating-runs polynomial enumerates alternating runs in the symmetric group. There are three formulae for the number of permutations, $R_{n,k}$ in $\mathfrak{S}_n$ with $k$ alternating runs, but all of them are complicated. We show that when enumerated with sign taken into account, one gets a {\it neat formula}. As a consequence, we get a near refinement of a result of Wilf on the exponent of $(1+t)$ when it divides the alternating-runs polynomial in the alternating group $\mathcal{A}_n$. Other applications include a moment-type identity and enumeration of alternating permutations in $\mathcal{A}_n$. Similar results are obtained for the type B and type D Coxeter groups.

Chat View PDF

Log-concavity of the Excedance Enumerators in positive elements of Type A and Type B Coxeter Groups

2020-09-22

Hiranya Kishore Dey

The classical Eulerian Numbers $A_{n,k}$ are known to be log-concave. Let $P_{n,k}$ and $Q_{n,k}$ be the number of even and odd permutations with $k$ excedances. In this paper, we show … The classical Eulerian Numbers $A_{n,k}$ are known to be log-concave. Let $P_{n,k}$ and $Q_{n,k}$ be the number of even and odd permutations with $k$ excedances. In this paper, we show that $P_{n,k}$ and $Q_{n,k}$ are log-concave. For this, we introduce the notion of strong synchronisation and ratio-alternating which are motivated by the notion of synchronisation and ratio-dominance, introduced by Gross, Mansour, Tucker and Wang in 2014. We show similar results for Type B Coxeter Groups. We finish with some conjectures to emphasize the following: though strong synchronisation is stronger than log-concavity, many pairs of interesting combinatorial families of sequences seem to satisfy this property.

Chat View PDF

Gamma Positivity of the Excedance-Based Eulerian Polynomial in Positive Elements of Classical Weyl Groups

2020-09-20

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

Chat View PDF

On Determining Number of Kneser Graphs

2020-09-17

Angsuman Das , Hiranya Kishore Dey

The determining number of a graph $G = (V,E)$ is the minimum cardinality of a set $S\subseteq V$ such that pointwise stabilizer of $S$ under the action of $Aut(G)$ is … The determining number of a graph $G = (V,E)$ is the minimum cardinality of a set $S\subseteq V$ such that pointwise stabilizer of $S$ under the action of $Aut(G)$ is trivial. In this paper, we prove some improved upper and lower bounds on the determining number of Kneser graphs. Moreover, we compute the exact value of the determining number for some subfamilies of Kneser graphs. Finally, we show that the number of Kneser graphs with a given determining number $r$ is an increasing function of $r$.

Chat View PDF

On the Alternating runs polynomial in type B and D Coxeter Groups

2020-09-07

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

Wilf showed that the the alternating runs polynomial $R_n(t)$ counting the number of permutations in the Symmetric group is divisible by $(1+t)^m$ where $m = \lfloor (n-2)/2 \rfloor$. Recently, Bona … Wilf showed that the the alternating runs polynomial $R_n(t)$ counting the number of permutations in the Symmetric group is divisible by $(1+t)^m$ where $m = \lfloor (n-2)/2 \rfloor$. Recently, Bona gave a group action based proof. Type B and D analogues of Wilf's result are known. In this note, we extend Bona's proof to prove the type B and D analogue.

Chat View PDF

Gamma Positivity of the Descent Based Eulerian Polynomial in Positive Elements of Classical Weyl Groups

2020-08-07

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

The Eulerian polynomial $A_n(t)$ enumerating descents in $\mathfrak{S}_n$ is known to be gamma positive for all $n$. When enumeration is done over the type B and type D Coxeter groups, … The Eulerian polynomial $A_n(t)$ enumerating descents in $\mathfrak{S}_n$ is known to be gamma positive for all $n$. When enumeration is done over the type B and type D Coxeter groups, the type B and type D Eulerian polynomials are also known to be gamma positive for all $n$. We consider $A_n^+(t)$ and $A_n^-(t)$, the polynomials which enumerate descents in the alternating group $\mathcal{A}_n$ and in $\mathfrak{S}_n - \mathcal{A}_n$ respectively. We show the following results about $A_n^+(t)$ and $A_n^-(t)$: both polynomials are gamma positive iff $n \equiv 0,1$ (mod 4). When $n \equiv 2,3$ (mod 4), both polynomials are not palindromic. When $n \equiv 2$ (mod 4), we show that {\sl two} gamma positive summands add up to give $A_n^+(t)$ and $A_n^-(t)$. When $n \equiv 3$ (mod 4), we show that {\sl three} gamma positive summands add up to give both $A_n^+(t)$ and $A_n^-(t)$.  We show similar gamma positivity results about the descent based type B and type D Eulerian polynomials when enumeration is done over the positive elements in the respective Coxeter groups. We also show that the polynomials considered in this work are unimodal.

Chat View PDF

On the connectivity of enhanced power graph of finite group

2020-01-01

Sudip Bera , Hiranya Kishore Dey , Sajal Kumar Mukherjee

This paper deals with the vertex connectivity of enhanced power graph of finite group. We classify all abelian groups G such that vertex connectivity of enhanced power graph of G … This paper deals with the vertex connectivity of enhanced power graph of finite group. We classify all abelian groups G such that vertex connectivity of enhanced power graph of G is 1. We derive an upper bound of vertex connectivity for the enhanced power graph of any general abelian group G. Also we completely characterize all abelian group G, such that the proper enhanced power graph is connected. Moreover, we study some special class of non-abelian group G such that the proper enhanced power graph is connected and we find their vertex connectivity.

Chat View PDF

Signed Alternating-runs enumeration in Classical Weyl Groups

2020-01-01

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

Chat View PDF

Log-concavity of the Excedance Enumerators in positive elements of Type A and Type B Coxeter Groups

2020-01-01

Hiranya Kishore Dey

Chat View PDF

Determining Number of Kneser Graphs: Exact Values and Improved Bounds

2020-01-01

Angsuman Das , Hiranya Kishore Dey

Chat View PDF

On the Alternating runs polynomial in type B and D Coxeter Groups

2020-01-01

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

Wilf showed that the the alternating runs polynomial $R_n(t)$ counting the number of permutations in the Symmetric group is divisible by $(1+t)^m$ where $m = \lfloor (n-2)/2 \rfloor$. Recently, B\'{o}na … Wilf showed that the the alternating runs polynomial $R_n(t)$ counting the number of permutations in the Symmetric group is divisible by $(1+t)^m$ where $m = \lfloor (n-2)/2 \rfloor$. Recently, B\'{o}na gave a group action based proof. Type B and D analogues of Wilf's result are known. In this note, we extend B\'{o}na's proof to prove the type B and D analogue.

Chat View PDF

Eulerian Central Limit Theorems and Carlitz identities in positive elements of Classical Weyl Groups

2020-01-01

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

Central Limit Theorems are known for the Eulerian statistic "descent" (or "excedance") in the symmetric group $\SSS_n$. Recently, Fulman, Kim, Lee and Petersen gave a Central Limit Theorem for "descent" … Central Limit Theorems are known for the Eulerian statistic "descent" (or "excedance") in the symmetric group $\SSS_n$. Recently, Fulman, Kim, Lee and Petersen gave a Central Limit Theorem for "descent" over the alternating group $\AAA_n$ and also gave a Carlitz identity in $\AAA_n$ using descents. In this paper, we give a Central Limit Theorem in $\AAA_n$ involving excedances. We extend these to the positive elements in type B and type D Coxeter groups. Boroweic and M\l{}otkowski enumerated type B descents over $\DD_n$, the type D Coxeter group and gave similar results. We refine their results for both the positive and negative part of $\DD_n$. Our results are a consequence of signed enumeration over these subsets.

Chat View PDF

Combinatorial proof of the log-convexity for the derangements in the Coxeter groups

2020-01-01

Hiranya Kishore Dey , Subhajit Ghosh

Chat View PDF

Gamma positivity of the Excedance based Eulerian polynomial in positive elements of Classical Weyl Groups

2018-12-05

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

The classical Eulerian polynomials $A_n(t)$ are known to be gamma positive. Define the positive Eulerian polynomial $\mathsf{AExc^{+}}_n(t)$ as the polynomial obtained when we sum excedances over the alternating group. We … The classical Eulerian polynomials $A_n(t)$ are known to be gamma positive. Define the positive Eulerian polynomial $\mathsf{AExc^{+}}_n(t)$ as the polynomial obtained when we sum excedances over the alternating group. We show that $\mathsf{AExc^{+}}_n(t)$ is gamma positive iff $n \geq 5$ and $n \equiv 1$ (mod 2). When $n \geq 4$, and $n \equiv 0$ (mod 2) we show that $\mathsf{AExc^{+}}_n(t)$ can be written as a sum of two gamma positive polynomials. Similar results are shown when we consider the positive type-D and type-D Eulerian polynomials. Finally, we show gamma positivity results when we sum excedances over derangements with positive and negative sign. Our main resuls is that the polynomial obtained by summing excedance over a conjugacy class indexed by $\lambda$ is gamma positive.

Chat View PDF

Gamma positivity of the Excedance based Eulerian polynomial in positive elements of Classical Weyl Groups

2018-01-01

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

Chat View PDF

Gamma positivity of the Descent based Eulerian polynomial in positive elements of Classical Weyl Groups

2018-01-01

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

The classical Eulerian polynomials $A_n(t)$ are known to be gamma positive. Define the positive Eulerian polynomial $A_n^+(t)$ as the polynomial obtained when we sum descents over the alternating group. We … The classical Eulerian polynomials $A_n(t)$ are known to be gamma positive. Define the positive Eulerian polynomial $A_n^+(t)$ as the polynomial obtained when we sum descents over the alternating group. We show that $A_n^+(t)$ is gamma positive iff $n \equiv 0,1$ (mod 4). When $n \equiv 2$ (mod 4) we show that $A_n^+(t)$ can be written as a sum of two gamma positive polynomials while if $n \equiv 3$ (mod 4), we show that $A_n^+(t)$ can be written as a sum of three gamma positive polynomials. Similar results are shown when we consider the positive type-D and type-D Eulerian polynomials.

Chat View PDF

Common Coauthors

Coauthor	Papers Together
Sivaramakrishnan Sivasubramanian	16
Sudip Bera	8
Angsuman Das	6
Peter J‎. Cameron	4
Umesh Shankar	3
Subhajit Ghosh	2
Archita Mondal	2
Sajal Kumar Mukherjee	2
Sucharita Biswas	2
S. Venkitesh	1
Anita Arora	1
Digjoy Paul	1
Iswar Mahato	1
Arvind Ayyer	1
Kamal Lochan Patra	1
Shivani Goel	1
Soumyajit Saha	1
Brahadeesh Sankarnarayanan	1
Binod Kumar Sahoo	1

Commonly Cited References

Signed Excedance Enumeration in the Hyperoctahedral group

2014-04-16

Sivaramakrishnan Sivasubramanian

Several signed excedance-like statistics have nice formulae or generating functions when summed over the symmetric group and over its subset of derangements. We give counterparts of some of these results … Several signed excedance-like statistics have nice formulae or generating functions when summed over the symmetric group and over its subset of derangements. We give counterparts of some of these results when we sum over the hyperoctahedral group and its subset of derangements. Our results motivate us to define and derive attractive bivariate formulae which generalise some of these results for the symmetric group.

Chat View PDF

Descents and one-dimensional characters for classical Weyl groups

1995-06-01

Victor Reiner

Undirected power graphs of semigroups

2009-01-26

Ivy Chakrabarty , Susmita Ghosh , M. K. Sen

On the Structure of the Power Graph and the Enhanced Power Graph of a Group

2017-07-28

Ghodratollah Aalipour , Saieed Akbari , Peter J‎. Cameron +2 more

Let $G$ be a group‎. ‎The power graph of $G$ is a graph with the vertex‎ ‎set $G$‎, ‎having an edge between two elements whenever one is a power of … Let $G$ be a group‎. ‎The 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 commuting graph by introducing a new graph which lies in between‎. ‎We call this new graph as the enhanced power graph‎. ‎For an arbitrary pair of these three graphs we characterize finite groups for which this pair of graphs are equal‎.

Chat View PDF

q-Eulerian Polynomials Arising from Coxeter Groups

1994-09-01

Francesco Brenti

A Combinatorial Proof of the Log-Concavity of the Numbers of Permutations with k Runs

2000-05-01

Miklós Bóna , Richard Ehrenborg

Chat View PDF

On Groups of Even Order

1955-11-01

Richard Brauer , Kenneth Arthur Fowler

odd order are soluble. We shall use the term involution for a group element of order 2. If m is the total number of involutions of 65 and if we … odd order are soluble. We shall use the term involution for a group element of order 2. If m is the total number of involutions of 65 and if we set n = g/m, the same method shows that 65 contains a normal subgroup V distinct from 5 such that the index of V is either 2 or is less than [n(n + 2)/2]! (where [x] denotes the largest integer not exceeding the real number x). If J is an involution in 65 and if n(J) is the order of its normalizer 91(J) in 5, then n < n(J). It then follows that there exist only a finite number of simple groups in which the normalizer of an involution is isomorphic to a given group.

On the Connectivity and Independence Number of Power Graphs of Groups

2020-03-31

Peter J‎. Cameron , Sayyed Heidar Jafari

Abstract Let G be a group. The power graph of G is a graph with vertex set G in which two distinct elements x , y are adjacent if one … Abstract Let G be a group. The power graph of G is a graph with vertex set G in which two distinct elements x , y are adjacent if one of them is a power of the other. We characterize all groups whose power graphs have finite independence number, show that they have clique cover number equal to their independence number, and calculate this number. The proper power graph is the induced subgraph of the power graph on the set $$G-\{1\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>G</mml:mi><mml:mo>-</mml:mo><mml:mo>{</mml:mo><mml:mn>1</mml:mn><mml:mo>}</mml:mo></mml:mrow></mml:math> . A group whose proper power graph is connected must be either a torsion group or a torsion-free group; we give characterizations of some groups whose proper power graphs are connected.

Chat View PDF

Power graphs: A survey

2013-11-13

Jemal Abawajy , Andrei Kelarev , Morshed Chowdhury

This article gives a survey of all results on the power graphs of groups and semigroups obtained in the literature. Various conjectures due to other authors, questions and open problems … This article gives a survey of all results on the power graphs of groups and semigroups obtained in the literature. Various conjectures due to other authors, questions and open problems are also included.

Chat View PDF

Binomial coefficients and anti-exceedances of even permutations: A combinatorial proof

1993-07-01

Roberto Mantaci

On certain combinatorial expansions of the Eulerian polynomials

2007-12-01

Chak-On Chow

On bounding the diameter of the commuting graph of a group

2014-01-01

Michael Giudici , Aedan Pope

Abstract. The commuting graph of a group Abstract. The commuting graph of a group

Chat View PDF

The commuting graph of the symmetric inverse semigroup

2015-03-28

João Araújo , Wolfram Bentz , Janusz Konieczny

Chat View PDF

On the intersection power graph of a finite group

2018-04-03

Sudip Bera

Given a group G , the intersection power graph of G , denoted by G I ( G ) , is the graph with vertex set G and two distinct … Given a group G , the intersection power graph of G , denoted by G I ( G ) , is the graph with vertex set G and two distinct vertices x and y are adjacent in G I ( G ) if there exists a non-identity element z ∈ G such that x m =z=y n , for some m , n ∈ N , i.e. x ∼ y in G I ( G ) if ⟨ x ⟩ ∩ ⟨ y ⟩ ≠ { e } and e is adjacent to all other vertices, where e is the identity element of the group G . Here we show that the graph G I ( G ) is complete if and only if either G is cyclic p -group or G is a generalized quaternion group. Furthermore, G I ( G ) is Eulerian if and only if ∣ G ∣ is odd. We characterize all abelian groups and also all non-abelian p -groups G , for which G I ( G ) is dominatable. Beside, we determine the automorphism group of the graph G I (Z n ) , when n ≠ p m .

Chat View PDF

Automorphism groups of supergraphs of the power graph of a finite group

2016-10-12

Asma Hamzeh , Али Реза Ашрафи

Gamma Positivity of the Descent Based Eulerian Polynomial in Positive Elements of Classical Weyl Groups

2020-08-07

Hiranya Kishore Dey , Sivaramakrishnan Sivasubramanian

Chat View PDF

Unimodal, log-concave and Pólya frequency sequences in combinatorics

1989-01-01

Francesco Brenti

Un grand nombre de suites d'interet combinatoire sont unimodales ou log-concaves. Il s'agit de proprietes difficiles a montrer et non conservees par des transformations lineaires, en general. On peut affiner … Un grand nombre de suites d'interet combinatoire sont unimodales ou log-concaves. Il s'agit de proprietes difficiles a montrer et non conservees par des transformations lineaires, en general. On peut affiner ces deux notions pour definir les suites de frequences de Polya qui possedent des proprietes plus convenables. On montre des applications combinatoires diverses, telle que la coloration de graphes, de ces suites

Chat View PDF

Signed excedance enumeration via determinants

2011-04-15

Sivaramakrishnan Sivasubramanian

On enhanced power graphs of finite groups

2017-07-19

Sudip Bera , A. K. Bhuniya

Given a group [Formula: see text], the enhanced power graph of [Formula: see text], denoted by [Formula: see text], is the graph with vertex set [Formula: see text] and two … Given a group [Formula: see text], the enhanced power graph of [Formula: see text], denoted by [Formula: see text], is the graph with vertex set [Formula: see text] and two distinct vertices [Formula: see text] and [Formula: see text] are edge connected in [Formula: see text] if there exists [Formula: see text] such that [Formula: see text] and [Formula: see text] for some [Formula: see text]. Here, we show that the graph [Formula: see text] is complete if and only if [Formula: see text] is cyclic; and [Formula: see text] is Eulerian if and only if [Formula: see text] is odd. We characterize all abelian groups and all non-abelian [Formula: see text]-groups [Formula: see text] such that [Formula: see text] is dominatable. Besides, we show that there is a one-to-one correspondence between the maximal cliques in [Formula: see text] and the maximal cyclic subgroups of [Formula: see text].

Cayley graphs as classifiers for data mining: The influence of asymmetries

2009-01-02

Andrei Kelarev , Joe Ryan , John Yearwood

Log‐Concave and Unimodal Sequences in Algebra, Combinatorics, and Geometry<sup>a</sup>

1989-12-01

Richard P. Stanley

Runs, Slides and Moments

1983-12-01

Louis W. Shapiro , Wen-Jin Woan , Seyoum Getu

The moments of a Catalan triangle are computed. The method is similar to that used for probability generating functions. This however does not explain the elegance of the results until … The moments of a Catalan triangle are computed. The method is similar to that used for probability generating functions. This however does not explain the elegance of the results until further combinatorial connections are developed. These include Eulerian numbers, runs, zig-zag permutations, tangent numbers and a kind of nontrivial run called a slide.

Inductive and injective proofs of log concavity results

1988-01-01

Bruce E. Sagan

Vertex connectivity of the power graph of a finite cyclic group

2018-06-25

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

Chat View PDF

Counting permutations by their alternating runs

2007-06-23

E. Rodney Canfield , Herbert S. Wilf

On the Connectivity of Proper Power Graphs of Finite Groups

2015-07-06

Alireza Doostabadi , Mohammad Farrokhi Derakhshandeh Ghouchan

We study the connectivity of proper power graphs of some family of finite groups including nilpotent groups, groups with a nontrivial partition, and symmetric and alternating groups. Also, for such … We study the connectivity of proper power graphs of some family of finite groups including nilpotent groups, groups with a nontrivial partition, and symmetric and alternating groups. Also, for such a group, the corresponding proper power graph has diameter at most 26 whenever it is connected.

Chat View PDF

Minimal cut-sets in the power graphs of certain finite non-cyclic groups

2020-10-16

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

We study minimal cut-sets of the power graph of a finite non-cyclic nilpotent group which are associated with its maximal cyclic subgroups. As a result, we find the vertex connectivity … We study minimal cut-sets of the power graph of a finite non-cyclic nilpotent group which are associated with its maximal cyclic subgroups. As a result, we find the vertex connectivity of the power graphs of certain finite non-cyclic abelian groups whose order is divisible by at most three distinct primes.

Chat View PDF

An explicit formula for the number of permutations with a given number of alternating runs

2012-05-26

Shi-Mei Ma

Chat View PDF

On the Connectivity of Enhanced Power Graphs of Finite Groups

2021-01-03

Sudip Bera , Hiranya Kishore Dey , Sajal Kumar Mukherjee

Enriched P-partitions and peak algebras

2006-07-21

T. Kyle Petersen

Chat View PDF

Longest alternating subsequences of permutations

2008-08-01

Richard P. Stanley

The length is(w) of the longest increasing subsequence of a permutation w in the symmetric group Sn has been the object of much investigation. We develop comparable results for the … The length is(w) of the longest increasing subsequence of a permutation w in the symmetric group Sn has been the object of much investigation. We develop comparable results for the length as(w) of the longest alternating subsequence of w, where a sequence a, b, c, d, . . . is alternating if a > b d < · · · . For instance, the expected value (mean) of as(w) for w ∈ Sn is exactly (4n + 1)/6 if n ≥ 2.

Chat View PDF

On co-maximal subgroup graph of a group

2022-06-23

Angsuman Das , Manideepa Saha , Saba Al-Kaseasbeh

Chat View PDF

A study of enhanced power graphs of finite groups

2019-03-04

Samir Zahirović , Ivica Bošnjak , Rozália Madarász

The enhanced power graph [Formula: see text] of a group [Formula: see text] is the graph with vertex set [Formula: see text] such that two vertices [Formula: see text] and … The enhanced power graph [Formula: see text] of a group [Formula: see text] is the graph with vertex set [Formula: see text] such that two vertices [Formula: see text] and [Formula: see text] are adjacent if they are contained in the same cyclic subgroup. We prove that finite groups with isomorphic enhanced power graphs have isomorphic directed power graphs. We show that any isomorphism between undirected power graph of finite groups is an isomorphism between enhanced power graphs of these groups, and we find all finite groups [Formula: see text] for which [Formula: see text] is abelian, all finite groups [Formula: see text] with [Formula: see text] being prime power, and all finite groups [Formula: see text] with [Formula: see text] being square-free. Also, we describe enhanced power graphs of finite abelian groups. Finally, we give a characterization of finite nilpotent groups whose enhanced power graphs are perfect, and we present a sufficient condition for a finite group to have weakly perfect enhanced power graph.

The symmetric and unimodal expansion of Eulerian polynomials via continued fractions

2011-10-17

Heesung Shin , Jiang Zeng

Chat View PDF

The signed Eulerian numbers

1992-04-01

Jacques Désarménien , Dominique Foata

Counting signed permutations by their alternating runs

2014-02-06

Chak-On Chow , Shi-Mei Ma

The purpose of this paper is to establish a connection between alternating runs of signed permutations in the hyperoctahedral group and left peaks of permutations in the symmetric group, and … The purpose of this paper is to establish a connection between alternating runs of signed permutations in the hyperoctahedral group and left peaks of permutations in the symmetric group, and then to study some associated enumerative polynomials of signed permutations. Properties of these enumerative polynomials, including combinatorial formulas and recurrence relations are studied. In particular, we deduce a convolution formula connecting the number of alternating runs of permutations in the symmetric group to that in the hyperoctahedral group.

Symmetric unimodal expansions of excedances in colored permutations

2015-11-03

Heesung Shin , Jiang Zeng

Chat View PDF

The metric dimension of the enhanced power graph of a finite group

2019-01-21

Xuanlong Ma , Yanhong She

The enhanced power graph of a finite group [Formula: see text] is the graph whose vertex set is [Formula: see text], and two distinct vertices are adjacent if they generate … The enhanced power graph of a finite group [Formula: see text] is the graph whose vertex set is [Formula: see text], and two distinct vertices are adjacent if they generate a cyclic subgroup of [Formula: see text]. In this paper, we establish an explicit formula for the metric dimension of an enhanced power graph. As an application, we compute the metric dimension of the enhanced power graph of an elementary abelian [Formula: see text]-group, a dihedral group and a generalized quaternion group.

Actions on permutations and unimodality of descent polynomials

2007-03-02

Petter Brändén

Chat View PDF

An ideal based zero-divisor graph of a commutative semiring

2009-05-21

Shahabaddin Ebrahimi Atani

There is a natural graph associated to the zero-divisors of a commutative semiring with non-zero identity.In this article we essentially study zero-divisor graphs with respect to primal and non-primal ideals … There is a natural graph associated to the zero-divisors of a commutative semiring with non-zero identity.In this article we essentially study zero-divisor graphs with respect to primal and non-primal ideals of a commutative semiring R and investigate the interplay between the semiring-theoretic properties of R and the graph-theoretic properties of Γ I (R) for some ideal I of R. We also show that the zero-divisor graph with respect to primal ideals commutes by the semiring of fractions of R.

Enumeration of Type D Permutations with Alternating Runs

2018-05-16

Emily X. L. Gao , Brian Y. Sun

Gamma-positivity in combinatorics and geometry

2017-11-16

Christos A. Athanasiadis

Gamma-positivity is an elementary property that polynomials with symmetric coefficients may have, which directly implies their unimodality. The idea behind it stems from work of Foata, Sch\utzenberger and Strehl on … Gamma-positivity is an elementary property that polynomials with symmetric coefficients may have, which directly implies their unimodality. The idea behind it stems from work of Foata, Sch\utzenberger and Strehl on the Eulerian polynomials; it was revived independently by Br\and\'en and Gal in the course of their study of poset Eulerian polynomials and face enumeration of flag simplicial spheres, respectively, and has found numerous applications since then. This paper surveys some of the main results and open problems on gamma-positivity, appearing in various combinatorial or geometric contexts, as well as some of the diverse methods that have been used to prove it.

Chat View PDF

A survey of alternating permutations

2010-01-01

Richard P. Stanley

We survey some aspects of the theory of alternating permutations, beginning with the famous result of André that if En is the number of alternating permutations of 1, 2, . … We survey some aspects of the theory of alternating permutations, beginning with the famous result of André that if En is the number of alternating permutations of 1, 2, . . ., n, then P n≥0 En x n n! = sec x + tan x.Topics include refinements and q-analogues of En, various occurrences of En in mathematics, longest alternating subsequences of permutations, umbral enumeration of special classes of alternating permutations, and the connection between alternating permutations and the cd-index of the symmetric group.

Chat View PDF

Signed Mahonians

2004-10-05

Ron M. Adin , Ira M. Gessel , Yuval Roichman

The Zero-Divisor Graph of a Commutative Ring

1999-07-01

David F. Anderson , Philip S. Livingston

The determining number of Kneser graphs

2013-01-28

José Cáceres , Delia Garijo , Antonio González +2 more

Graph Theory A set of vertices S is a determining set of a graph G if every automorphism of G is uniquely determined by its action on S. The determining … Graph Theory A set of vertices S is a determining set of a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G is the minimum cardinality of a determining set of G. This paper studies the determining number of Kneser graphs. First, we compute the determining number of a wide range of Kneser graphs, concretely Kn:k with n≥k(k+1) / 2+1. In the language of group theory, these computations provide exact values for the base size of the symmetric group Sn acting on the k-subsets of 1,..., n. Then, we establish for which Kneser graphs Kn:k the determining number is equal to n-k, answering a question posed by Boutin. Finally, we find all Kneser graphs with fixed determining number 5, extending the study developed by Boutin for determining number 2, 3 or 4.

Chat View PDF

Some results on the power graphs of finite groups

2015-01-01

Doostabadi Alireza , Emy Zairah Ahmad , Abbas Jafarzadeh

We classify planar graphs and complete power graphs of groups and show that the only infinite group with a complete power graph is the Prüfer group p ∞ .Clique and … We classify planar graphs and complete power graphs of groups and show that the only infinite group with a complete power graph is the Prüfer group p ∞ .Clique and chromatic numbers and the automorphism group of power graphs are investigated.We also prove that the reduced power graph of a group G is regular if and only if G is a cyclic p-group or exp(G) = p for some prime number p.

Chat View PDF

Vertex connectivity of the power graph of a finite cyclic group II

2019-02-08

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

The power graph [Formula: see text] of a given finite group [Formula: see text] is the simple undirected graph whose vertices are the elements of [Formula: see text], in which … The power graph [Formula: see text] of a given finite group [Formula: see text] is the simple undirected graph whose vertices are the elements of [Formula: see text], in which two distinct vertices are adjacent if and only if one of them can be obtained as an integral power of the other. The vertex connectivity [Formula: see text] of [Formula: see text] is the minimum number of vertices which need to be removed from [Formula: see text] so that the induced subgraph of [Formula: see text] on the remaining vertices is disconnected or has only one vertex. For a positive integer [Formula: see text], let [Formula: see text] be the cyclic group of order [Formula: see text]. Suppose that the prime power decomposition of [Formula: see text] is given by [Formula: see text], where [Formula: see text], [Formula: see text] are positive integers and [Formula: see text] are prime numbers with [Formula: see text]. The vertex connectivity [Formula: see text] of [Formula: see text] is known for [Formula: see text], see [Panda and Krishna, On connectedness of power graphs of finite groups, J. Algebra Appl. 17(10) (2018) 1850184, 20 pp, Chattopadhyay, Patra and Sahoo, Vertex connectivity of the power graph of a finite cyclic group, to appear in Discr. Appl. Math., https://doi.org/10.1016/j.dam.2018.06.001]. In this paper, for [Formula: see text], we give a new upper bound for [Formula: see text] and determine [Formula: see text] when [Formula: see text]. We also determine [Formula: see text] when [Formula: see text] is a product of distinct prime numbers.

Chat View PDF

Identifying Graph Automorphisms Using Determining Sets

2006-09-07

Debra Boutin

A set of vertices $S$ is a determining set for a graph $G$ if every automorphism of $G$ is uniquely determined by its action on $S$. The determining number of … A set of vertices $S$ is a determining set for a graph $G$ if every automorphism of $G$ is uniquely determined by its action on $S$. The determining number of a graph is the size of a smallest determining set. This paper describes ways of finding and verifying determining sets, gives natural lower bounds on the determining number, and shows how to use orbits to investigate determining sets. Further, determining sets of Kneser graphs are extensively studied, sharp bounds for their determining numbers are provided, and all Kneser graphs with determining number $2$, $3,$ or $4$ are given.

Chat View PDF

Eulerian quasisymmetric functions

2010-09-07

John Shareshian , Michelle L. Wachs

Chat View PDF