Kamal Lochan Patra

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.

View PDF Chat

Maximizing the distance between center, centroid and characteristic set of a tree

2007-03-30

Kamal Lochan Patra

Abstract Consider a tree Pn-g,g , n≥ 2, 1≤ g≤ n-1 on n vertices which is obtained from a path on [1,2, … ,n-g] vertices by adding g pendant vertices … Abstract Consider a tree Pn-g,g , n≥ 2, 1≤ g≤ n-1 on n vertices which is obtained from a path on [1,2, … ,n-g] vertices by adding g pendant vertices to the pendant vertex n-g. We prove that over all trees on n ≥ 5 vertices, the distance between center and characteristic set, centroid and characteristic set, and center and centroid is maximized by trees of the form Pn-g,g , 2 ≤ g ≤ n-3. For n≥ 5, we also supply the precise location of the characteristic set of the tree Pn-g,g , 2 ≤ g ≤ n-3. Keywords: TreeLaplacian matrixAlgebraic connectivityCharacteristic setCenterCentroid Acknowledgement The author wishes to thank Prof. A. K. Lal and Prof. S. Pati for their help and guidance.

Bounds for the Laplacian spectral radius of graphs

2017-10-30

Kamal Lochan Patra , Binod Kumar Sahoo

This paper is a survey on the upper and lower bounds for the largest eigenvalue of the Laplacian matrix, known as the Laplacian spectral radius, of a graph. The bounds … This paper is a survey on the upper and lower bounds for the largest eigenvalue of the Laplacian matrix, known as the Laplacian spectral radius, of a graph. The bounds are given as functions of graph parameters like the number of vertices, the number of edges, degree sequence, average 2-degrees, diameter, covering number, domination number, independence number and other parameters.

View PDF Chat

Minimum size blocking sets of certain line sets related to a conic in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:mi>P</mml:mi><mml:mi>G</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mi>q</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math>

2016-02-23

Kamal Lochan Patra , Binod Kumar Sahoo , Bikramaditya Sahu

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.

View PDF Chat

Wiener index of graphs with fixed number of pendant or cut-vertices

2022-02-28

Dinesh Pandey , Kamal Lochan Patra

View PDF Chat

On the number of connected subgraphs of graphs

2021-06-01

Dinesh Pandey , Kamal Lochan Patra

A non-abelian representation of the dual polar space DQ(2n,2)

2009-01-01

Kamal Lochan Patra , Binod Kumar Sahoo

We prove that the dual polar space DQ(2n, 2), n ≥ 3, of rank n associated with a non-singular parabolic quadric in PG(2n, 2) admits a faithful non-abelian representation in … We prove that the dual polar space DQ(2n, 2), n ≥ 3, of rank n associated with a non-singular parabolic quadric in PG(2n, 2) admits a faithful non-abelian representation in the extraspecial 2-group 2 1+2 n + .The near 2n-gon I n (section 2.4) is a geometric hyperplane of DQ(2n, 2).For n ≥ 3, we first construct a faithful non-abelian representation of I n in 2 1+2 n + and subsequently extend it to a faithful non-abelian representation of DQ(2n, 2) in 2 1+2 n + .

View PDF Chat

On the minimum degree of the power graph of a finite cyclic group

2019-12-18

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

The power graph [Formula: see text] of a finite group [Formula: see text] is the undirected simple graph whose vertex set is [Formula: see text], in which two distinct vertices … The power graph [Formula: see text] of a finite group [Formula: see text] is the undirected simple graph whose vertex set is [Formula: see text], in which two distinct vertices are adjacent if one of them is an integral power of the other. For an integer [Formula: see text], let [Formula: see text] denote the cyclic group of order [Formula: see text] and let [Formula: see text] be the number of distinct prime divisors of [Formula: see text]. The minimum degree [Formula: see text] of [Formula: see text] is known for [Formula: see text], see [R. P. Panda and K. V. Krishna, On the minimum degree, edge-connectivity and connectivity of power graphs of finite groups, Comm. Algebra 46(7) (2018) 3182–3197]. For [Formula: see text], under certain conditions involving the prime divisors of [Formula: see text], we identify at most [Formula: see text] vertices such that [Formula: see text] is equal to the degree of at least one of these vertices. If [Formula: see text], or that [Formula: see text] is a product of distinct primes, we are able to identify two such vertices without any condition on the prime divisors of [Formula: see text].

View PDF Chat

On the super graphs and reduced super graphs of some finite groups

2023-10-11

Sandeep Dalal , Sanjay Mukherjee , Kamal Lochan Patra

View PDF Chat

Maximizing Laplacian spectral radius over trees with fixed diameter

2007-09-01

A. K. Lal , Kamal Lochan Patra

Abstract In this article, we consider the following problem: Of all trees on n vertices with diameter d (both fixed) which tree achieves the maximal Laplacian spectral radius? We show … Abstract In this article, we consider the following problem: Of all trees on n vertices with diameter d (both fixed) which tree achieves the maximal Laplacian spectral radius? We show that the maximal Laplacian spectral radius is obtained uniquely at , where is a tree obtained by taking a path P on d + 1 vertices and adding n-d-1 pendant vertices to a center point of P. Keywords: Bipartite graphTreeLaplacian spectral radiusDiameterCenter points Subject Classifications: O5C5O Acknowledgement The authors wish to thank Prof. S. Pati for bringing the problem and a few related references to our attention.

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

2018-02-21

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

The power graph of a group is the simple graph with vertices as the group elements, in which two distinct vertices are adjacent if and only if one of them … The power graph of a group is the simple graph with vertices as the group elements, in which two distinct vertices are adjacent if and only if one of them can be obtained as an integral power of the other. We study (minimal) cut-sets of the power graph of a (finite) non-cyclic (nilpotent) group which are associated with its maximal cyclic subgroups. Let $G$ be a finite non-cyclic nilpotent group whose order is divisible by at least two distinct primes. If $G$ has a Sylow subgroup which is neither cyclic nor a generalized quaternion $2$-group and all other Sylow subgroups of $G$ are cyclic, then under some conditions we prove that there is only one minimum cut-set of the power graph of $G$. We apply this result to 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.

Maximizing distance between center, centroid and subtree core of trees

2018-12-17

Dheer Noal Desai , Kamal Lochan Patra

The core index of a graph

2018-11-28

Dinesh Pandey , Kamal Lochan Patra

For a graph $G,$ we denote the number of connected subgraphs of $G$ by $F(G)$. For a tree $T$, $F(T)$ has been studied extensively and it has been observed that … For a graph $G,$ we denote the number of connected subgraphs of $G$ by $F(G)$. For a tree $T$, $F(T)$ has been studied extensively and it has been observed that $F(T)$ has a reverse correlation with Wiener index of $T$. Based on that, we call $F(G),$ the core index of $G$. In this paper, we characterize the graphs which extremize the core index among all graphs on $n$ vertices with $k\geq 0$ connected components. We extend our study of core index to unicyclic graphs and connected graphs with fixed number of pendant vertices. We obtained the unicyclic graphs which extremize the core index over all unicyclic graphs on $n$ vertices. The graphs which extremize the core index among all unicyclic graphs with fixed girth are also obtained. Among all connected graphs on $n$ vertices with fixed number of pendant vertices, the graph which minimizes and the graph which maximizes the core index are characterized.

Minimizing Laplacian spectral radius of unicyclic graphs with fixed girth

2013-12-01

Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

Extremizing the number of connected subgraphs of graphs

2018-11-28

Dinesh Pandey , Kamal Lochan Patra

For a graph $G,$ $F(G)$ denotes the number of connected subgraphs of $G.$ We call it as the core index of $G.$ In this paper, we characterize the graphs which … For a graph $G,$ $F(G)$ denotes the number of connected subgraphs of $G.$ We call it as the core index of $G.$ In this paper, we characterize the graphs which extremizes the core index among all graphs on $n$ vertices, among all unicyclic graphs on $n$ vertices, among all unicyclic graphs with fixed girth and among all connected graphs on $n$ vertices with fixed number of pendant vertices

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

2019-11-01

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

We retract [1, Lemma 3.4] as the statement is incorrect. In consequence, we correct the statements of Theorems 1.2 and 4.5 and their proofs. We retract [1, Lemma 3.4] as the statement is incorrect. In consequence, we correct the statements of Theorems 1.2 and 4.5 and their proofs.

Proper divisor graph of a positive integer

2020-01-01

Hitesh Kumar , Kamal Lochan Patra , Binod Kumar Sahoo

The proper divisor graph $Υ_n$ of a positive integer $n$ is the simple graph whose vertices are the proper divisors of $n$, and in which two distinct vertices $u, v$ … The proper divisor graph $Υ_n$ of a positive integer $n$ is the simple graph whose vertices are the proper divisors of $n$, and in which two distinct vertices $u, v$ are adjacent if and only if $n$ divides $uv$. The graph $Υ_n$ plays an important role in the study of the zero divisor graph of the ring $\mathbb{Z}_n$. In this paper, we study some graph theoretic properties of $Υ_n$ and determine the graph parameters such as clique number, chromatic number, chromatic index, independence number, matching number, domination number, vertex and edge covering numbers of $Υ_n$. We also determine the automorphism group of $Υ_n$.

Total eccentricity index of graphs with fixed number of pendant or cut vertices

2023-01-06

Dinesh Pandey , Kamal Lochan Patra

View PDF Chat

Different central parts of trees and their pairwise distances

2020-12-08

Dinesh Pandey , Kamal Lochan Patra

We determine the tree which maximizes the distance between characteristic set and subtree core over all trees on n vertices. The asymptotic nature of this distance is also discussed. The … We determine the tree which maximizes the distance between characteristic set and subtree core over all trees on n vertices. The asymptotic nature of this distance is also discussed. The problem of extremizing the distance between different central parts of trees on n vertices with fixed diameter is studied.

View PDF Chat

Characterizing finite nilpotent groups associated with a graph theoretic equality

2021-05-27

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

The power graph of a group is the simple graph whose vertices are the group elements and two vertices are adjacent whenever one of them is a positive power of … The power graph of a group is the simple graph whose vertices are the group elements and two vertices are adjacent whenever one of them is a positive power of the other. We characterize the finite nilpotent groups whose power graphs have equal vertex connectivity and minimum degree.

Characterizing finite nilpotent groups associated with a graph theoretic equality

2021-09-28

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

On the minimum cut-sets of the power graph of a finite cyclic group

2023-04-11

Sanjay Mukherjee , Kamal Lochan Patra , Binod Kumar Sahoo

The power graph [Formula: see text] of a finite group [Formula: see text] is the simple graph with vertex set [Formula: see text], in which two distinct vertices are adjacent … The power graph [Formula: see text] of a finite group [Formula: see text] is the simple graph with vertex set [Formula: see text], in which two distinct vertices are adjacent if one of them is a power of the other. For an integer [Formula: see text], let [Formula: see text] denote the cyclic group of order [Formula: see text] and let [Formula: see text] be the number of distinct prime divisors of [Formula: see text]. For [Formula: see text], the minimum cut-sets of [Formula: see text] are characterized in [S. Chattopadhyay, K. L. Patra and B. K. Sahoo, Vertex connectivity of the power graph of a finite cyclic group, Discrete Appl. Math. 266 (2019) 259–271]. In this paper, for [Formula: see text], we identify certain cut-sets of [Formula: see text] such that any minimum cut-set of [Formula: see text] must be one of them.

View PDF Chat

Spectrum of super commuting graphs of some finite groups

2024-07-30

Sandeep Dalal , Sanjay Mukherjee , Kamal Lochan Patra

Abstract Let $$\Gamma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Γ</mml:mi> </mml:math> be a simple finite graph with vertex set $$V(\Gamma )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>Γ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and edge set … Abstract Let $$\Gamma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Γ</mml:mi> </mml:math> be a simple finite graph with vertex set $$V(\Gamma )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>Γ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and edge set $$E(\Gamma )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>E</mml:mi> <mml:mo>(</mml:mo> <mml:mi>Γ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Let $$\mathcal {R}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>R</mml:mi> </mml:math> be an equivalence relation on $$V(\Gamma )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>Γ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . The $$\mathcal {R}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>R</mml:mi> </mml:math> -super $$\Gamma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Γ</mml:mi> </mml:math> graph $$\Gamma ^{\mathcal {R}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>Γ</mml:mi> <mml:mi>R</mml:mi> </mml:msup> </mml:math> is a simple graph with vertex set $$V(\Gamma )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>Γ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and two distinct vertices are adjacent if either they are in the same $$\mathcal {R}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>R</mml:mi> </mml:math> -equivalence class or there are elements in their respective $$\mathcal {R}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>R</mml:mi> </mml:math> -equivalence classes that are adjacent in the original graph $$\Gamma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Γ</mml:mi> </mml:math> . We first show that $$\Gamma ^{\mathcal {R}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>Γ</mml:mi> <mml:mi>R</mml:mi> </mml:msup> </mml:math> is a generalized join of some complete graphs and using this we obtain the adjacency and Laplacian spectrum of conjugacy super commuting graphs and order super commuting graphs of dihedral group $$D_{2n}\; (n\ge 3)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>D</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mspace/> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>3</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , generalized quaternion group $$Q_{4m} \;(m\ge 2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>Q</mml:mi> <mml:mrow> <mml:mn>4</mml:mn> <mml:mi>m</mml:mi> </mml:mrow> </mml:msub> <mml:mspace/> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> and the nonabelian group $$\mathbb {Z}_p \rtimes \mathbb {Z}_q$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>Z</mml:mi> <mml:mi>p</mml:mi> </mml:msub> <mml:mo>⋊</mml:mo> <mml:msub> <mml:mi>Z</mml:mi> <mml:mi>q</mml:mi> </mml:msub> </mml:mrow> </mml:math> of order pq , where p and q are distinct primes with $$q|(p-1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>q</mml:mi> <mml:mo>|</mml:mo> <mml:mo>(</mml:mo> <mml:mi>p</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> .

Center, centroid and subtree core of trees

2016-12-08

Dheer Noal Desai , Kamal Lochan Patra

For $n\geq 5$ and $2\leq g\leq n-3,$ consider the tree $P_{n-g,g}$ on $n$ vertices which is obtained by adding $g$ pendant vertices to one degree $1$ vertex of the path … For $n\geq 5$ and $2\leq g\leq n-3,$ consider the tree $P_{n-g,g}$ on $n$ vertices which is obtained by adding $g$ pendant vertices to one degree $1$ vertex of the path $P_{n-g}$. We call the trees $P_{n-g,g}$ as path-star trees. We prove that over all trees on $n\geq 5$ vertices, the distance between center and subtree core and the distance between centroid and subtree core are maximized by some path-star trees. We also prove that the tree $P_{n-g_0,g_0}$ maximizes both the distances among all path-star trees on $n$ vertices, where $g_0$ is the smallest positive integer such that $2^{g_0}+g_0>n-1.$

Laplacian eigenvalues of the zero divisor graph of the ring $\mathbb{Z}_{n}$

2019-03-19

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

We study the Laplacian eigenvalues of the zero divisor graph $\Gamma\left(\mathbb{Z}_{n}\right)$ of the ring $\mathbb{Z}_{n}$ and prove that $\Gamma\left(\mathbb{Z}_{p^t}\right)$ is Laplacian integral for every prime $p$ and positive integer $t\geq … We study the Laplacian eigenvalues of the zero divisor graph $\Gamma\left(\mathbb{Z}_{n}\right)$ of the ring $\mathbb{Z}_{n}$ and prove that $\Gamma\left(\mathbb{Z}_{p^t}\right)$ is Laplacian integral for every prime $p$ and positive integer $t\geq 2$. We also prove that the Laplacian spectral radius and the algebraic connectivity of $\Gamma\left(\mathbb{Z}_{n}\right)$ for most of the values of $n$ are, respectively, the largest and the second smallest eigenvalues of the vertex weighted Laplacian matrix of a graph which is defined on the set of proper divisors of $n$. The values of $n$ for which algebraic connectivity and vertex connectivity of $\Gamma\left(\mathbb{Z}_{n}\right)$ coincide are also characterized.

On the minimum degree of the power graph of a finite cyclic group

2019-05-26

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

The power graph $\mathcal{P}(G)$ of a finite group $G$ is the simple undirected graph whose vertex set is $G$, in which two distinct vertices are adjacent if one of them … The power graph $\mathcal{P}(G)$ of a finite group $G$ is the simple undirected graph whose vertex set is $G$, in which two distinct vertices are adjacent if one of them is an integral power of the other. For an integer $n\geq 2$, let $C_n$ denote the cyclic group of order $n$ and let $r$ be the number of distinct prime divisors of $n$. The minimum degree $\delta(\mathcal{P}(C_n))$ of $\mathcal{P}(C_n)$ is known for $r\in\{1,2\}$, see [18]. For $r\geq 3$, under certain conditions involving the prime divisors of $n$, we identify at most $r-1$ vertices such that $\delta(\mathcal{P}(C_n))$ is equal to the degree of at least one of these vertices. If $r=3$ or if $n$ is a product of distinct primes, we are able to identify two such vertices without any condition on the prime divisors of $n$.

Algebraic connectivity of connected graphs with fixed number of pendant vertices

2010-03-24

A. K. Lal , Kamal Lochan Patra , Binod Kumar Sahoo

In this paper we consider the following problem: Over the class of all simple connected graphs of order $n$ with $k$ pendant vertices ($n,k$ being fixed), which graph maximizes (respectively, … In this paper we consider the following problem: Over the class of all simple connected graphs of order $n$ with $k$ pendant vertices ($n,k$ being fixed), which graph maximizes (respectively, minimizes) the algebraic connectivity? We also discuss the algebraic connectivity of unicyclic graphs.

Minimizing Laplacian spectral radius of unicyclic graphs with fixed girth

2010-12-04

Kamal Lochan Patra , Binod Kumar Sahoo

In this paper we consider the following problem: Over the class of all simple connected unicyclic graphs on $n$ vertices with girth $g$ ($n,g$ being fixed), which graph minimizes the … In this paper we consider the following problem: Over the class of all simple connected unicyclic graphs on $n$ vertices with girth $g$ ($n,g$ being fixed), which graph minimizes the Laplacian spectral radius? We prove that the graph $U_{n,g}$ (defined in Section 1) uniquely minimizes the Laplacian spectral radius for $n\geq 2g-1$ when $g$ is even and for $n\geq 3g-1$ when $g$ is odd.

Different central parts of trees and their pairwise distances

2020-04-05

Dinesh Pandey , Kamal Lochan Patra

We determine the tree which maximizes the distance between characteristic set and subtree core over all trees on $n$ vertices. The asymptotic nature of this distance is also discussed. The … We determine the tree which maximizes the distance between characteristic set and subtree core over all trees on $n$ vertices. The asymptotic nature of this distance is also discussed. The problem of extremizing the distance between different central parts of trees on $n$ vertices with fixed diameter is studied

A Conjecture on Different Central Parts of Binary Trees

2022-11-19

Dinesh Pandey , Kamal Lochan Patra

View PDF Chat

On the minimum degree of power graphs of finite nilpotent groups

2022-07-18

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

The power graph P(G) of a group G is the simple graph with vertex set G and two distinct vertices are adjacent if one of them is a positive power … The power graph P(G) of a group G is the simple graph with vertex set G and two distinct vertices are adjacent if one of them is a positive power of the other. For a finite noncyclic nilpotent group G, we study the minimum degree δ(P(G)) of P(G). Under some conditions involving the prime divisors of |G| and the Sylow subgroups of G, we identify certain vertices associated with the generators of maximal cyclic subgroups of G such that δ(P(G)) is the degree of one of them. As an application, we obtain δ(P(G)) for some classes of nilpotent groups G.

View PDF Chat

Some new central parts of connected graphs.

2021-10-02

Dinesh Pandey , Kamal Lochan Patra

The center, median and the security center are three central parts defined for any connected graph whereas the characteristic set, subtree core and core vertices are three central parts defined … The center, median and the security center are three central parts defined for any connected graph whereas the characteristic set, subtree core and core vertices are three central parts defined for trees only. We extend the concept of the characteristic set, subtree core and core vertices to general connected graphs and call them the characteristic center, subgraph core and core vertices, respectively. We show by examples that in a connected graph all the above six central parts can be different and also prove that for a connected vertex transitive graph each of the six central parts is the whole vertex set. Further it is shown that given any graph $G$, there exists a connected supergraph $G_{ch}$ of $G$ with the whole vertex set of $G$ as the characteristic center. Associated with the subgraph core and core vertices, we leave some unanswered question related to the graph centrality.

Some new central parts of connected graphs

2021-01-01

Dinesh Pandey , Kamal Lochan Patra

View PDF Chat

On the minimum degree of power graphs of finite nilpotent groups

2021-01-01

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

The power graph $\mathcal{P}(G)$ of a group $G$ is the simple graph with vertex set $G$ and two vertices are adjacent whenever one of them is a positive power of … The power graph $\mathcal{P}(G)$ of a group $G$ is the simple graph with vertex set $G$ and two vertices are adjacent whenever one of them is a positive power of the other. In this paper, for a finite noncyclic nilpotent group $G$, we study the minimum degree $\delta(\mathcal{P}(G))$ of $\mathcal{P}(G)$. Under some conditions involving the prime divisors of $|G|$ and the Sylow subgroups of $G$, we identify certain vertices associated with the generators of maximal cyclic subgroups of $G$ such that $\delta(\mathcal{P}(G))$ is equal to the degree of one of these vertices. As an application, we obtain $\delta(\mathcal{P}(G))$ for some classes of finite noncyclic abelian groups $G$.

Characterizing finite nilpotent groups associated with a graph theoretic equality

2021-01-01

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

Total eccentricity index of graphs with fixed number of pendant or cut vertices

2020-01-01

Dinesh Pandey , Kamal Lochan Patra

The total eccentricity index of a connected graph is defined as sum of the eccentricities of all its vertices. We denote the set of all connected graphs on $n$ vertices … The total eccentricity index of a connected graph is defined as sum of the eccentricities of all its vertices. We denote the set of all connected graphs on $n$ vertices with $k$ pendant vertices by $\mathfrak{H}_{n,k}$ and denote the set of all connected graphs on $n$ vertices with $s$ cut vertices by $\mathfrak{C_{n,s}}$. In this paper, we give the sharp lower and upper bounds on the total eccentricity index over $\mathfrak{H}_{n,k}$ and the sharp lower bound for the same over $\mathfrak{C_{n,s}}$. We also provide the sharp upper bounds on the total eccentricity index over $\mathfrak{C_{n,s}}$ when $s=0,1,n-3,n-2$ and propose a problem regarding the upper bound over $\mathfrak{C_{n,s}}$ for $2\leq s\leq n-4.$

View PDF Chat

Different central parts of trees and their pairwise distances

2020-01-01

Dinesh Pandey , Kamal Lochan Patra

Laplacian eigenvalues of the zero divisor graph of the ring $\mathbb{Z}_{n}$

2019-01-01

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

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

2018-01-01

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

The power graph $\mathcal{P}(G)$ of a given finite group $G$ is the simple undirected graph whose vertices are the elements of $G$, in which two distinct vertices are adjacent if … The power graph $\mathcal{P}(G)$ of a given finite group $G$ is the simple undirected graph whose vertices are the elements of $G$, 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 $κ(\mathcal{P}(G))$ of $\mathcal{P}(G)$ is the minimum number of vertices which need to be removed from $G$ so that the induced subgraph of $\mathcal{P}(G)$ on the remaining vertices is disconnected or has only one vertex. For a positive integer $n$, let $C_n$ be the cyclic group of order $n$. Suppose that the prime power decomposition of $n$ is given by $n =p_1^{n_1}p_2^{n_2}\cdots p_r^{n_r}$, where $r\geq 1$, $n_1,n_2,\ldots, n_r$ are positive integers and $p_1,p_2,\ldots,p_r$ are prime numbers with $p_1

Center, centroid and subtree core of trees

2016-01-01

Dheer Noal Desai , Kamal Lochan Patra

View PDF Chat

On the minimum degree of the power graph of a finite cyclic group

2019-01-01

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

Wiener index of graphs with fixed number of pendant or cut vertices

2019-01-01

Dinesh Pandey , Kamal Lochan Patra

The Wiener index of a connected graph is defined as the sum of the distances between all unordered pair of its vertices. In this paper, we characterize the graphs which … The Wiener index of a connected graph is defined as the sum of the distances between all unordered pair of its vertices. In this paper, we characterize the graphs which extremize the Wiener index among all graphs on $n$ vertices with $k$ pendant vertices. We also characterize the graph which minimizes the Wiener index over the graphs on $n$ vertices with $s$ cut vertices.

View PDF Chat

On the minimum cut-sets of the power graph of a finite cyclic group

2022-01-01

Sanjay Mukherjee , Kamal Lochan Patra , Binod Kumar Sahoo

The power graph $\mathcal{P}(G)$ of a finite group $G$ is the simple graph with vertex set $G$, in which two distinct vertices are adjacent if one of them is a … The power graph $\mathcal{P}(G)$ of a finite group $G$ is the simple graph with vertex set $G$, in which two distinct vertices are adjacent if one of them is a power of the other. For an integer $n\geq 2$, let $C_n$ denote the cyclic group of order $n$ and let $r$ be the number of distinct prime divisors of $n$. The minimum cut-sets of $\mathcal{P}(C_n)$ are characterized in \cite{cps} for $r\leq 3$. In this paper, for $r\geq 4$, we identify certain cut-sets of $\mathcal{P}(C_n)$ such that any minimum cut-set of $\mathcal{P}(C_n)$ must be one of them.

View PDF Chat

Algebraic connectivity of connected graphs with fixed number of pendant vertices

2010-01-01

A. K. Lal , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

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

2018-01-01

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

On the minimum cut-sets of the power graph of a finite cyclic group, II

2025-05-21

Sanjay Mukherjee , Kamal Lochan Patra , Binod Kumar Sahoo

The power graph [Formula: see text] of a finite group [Formula: see text] is the simple graph with vertex set [Formula: see text] and two distinct vertices are adjacent if … The power graph [Formula: see text] of a finite group [Formula: see text] is the simple graph with vertex set [Formula: see text] and two distinct vertices are adjacent if one of them is a power of the other. Let [Formula: see text] where [Formula: see text] are primes with [Formula: see text] and [Formula: see text] are positive integers. For the cyclic group [Formula: see text] of order [Formula: see text], the minimum cut-sets of [Formula: see text] are characterized in [S. Chattopadhyay, K. L. Patra and B. K. Sahoo, Vertex connectivity of the power graph of a finite cyclic group, Discrete Appl. Math. 266 (2019) 259–271] for [Formula: see text]. Recently, in [S. Mukherjee, K. L. Patra and B. K. Sahoo, On the minimum cut-sets of the power graph of a finite cyclic group, J. Algebra Appl. 23(11) (2024) 2450176], certain cut-sets of [Formula: see text] are identified such that any minimum cut-set of [Formula: see text] must be one of them. In this paper, for [Formula: see text], we explicitly determine the minimum cut-sets, in particular, the vertex connectivity of [Formula: see text] when: (i) [Formula: see text], (ii) [Formula: see text] and [Formula: see text] and (iii) [Formula: see text], [Formula: see text], [Formula: see text].

On the domination number of proper power graphs of finite groups

2025-05-09

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

On the minimum cut-sets of the power graph of a finite cyclic group, II

2025-01-30

Sanjay Mukherjee , Kamal Lochan Patra , Binod Kumar Sahoo

The power graph $\mathcal{P}(G)$ of a finite group $G$ is the simple graph with vertex set $G$ and two distinct vertices are adjacent if one of them is a power … The power graph $\mathcal{P}(G)$ of a finite group $G$ is the simple graph with vertex set $G$ and two distinct vertices are adjacent if one of them is a power of the other. Let $n=p_1^{n_1}p_2^{n_2}\cdots p_r^{n_r},$ where $p_1,p_2,\ldots,p_r$ are primes with $p_1<p_2<\cdots <p_r$ and $n_1,n_2,\ldots, n_r$ are positive integers. For the cyclic group $C_n$ of order $n$, the minimum cut-sets of $\mathcal{P}(C_n)$ are characterized in \cite{cps} for $r\leq 3$. Recently, in \cite{MPS}, certain cut-sets of $\mathcal{P}(C_n)$ are identified such that any minimum cut-set of $\mathcal{P}(C_n)$ must be one of them. In this paper, for $r\geq 4$, we explicitly determine the minimum cut-sets, in particular, the vertex connectivity of $\mathcal{P}(C_n)$ when: (i) $n_r\geq 2$, (ii) $r=4$ and $n_r=1$, and (iii) $r=5$, $n_r=1$, $p_1\geq 3$.

View PDF Chat

Spectrum of super commuting graphs of some finite groups

2024-07-30

Sandeep Dalal , Sanjay Mukherjee , Kamal Lochan Patra

On vertex connectivity of zero-divisor graphs of finite commutative rings

2024-04-17

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

On the super graphs and reduced super graphs of some finite groups

2023-10-11

Sandeep Dalal , Sanjay Mukherjee , Kamal Lochan Patra

View PDF Chat

On the minimum cut-sets of the power graph of a finite cyclic group

2023-04-11

Sanjay Mukherjee , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

Total eccentricity index of graphs with fixed number of pendant or cut vertices

2023-01-06

Dinesh Pandey , Kamal Lochan Patra

View PDF Chat

A Conjecture on Different Central Parts of Binary Trees

2022-11-19

Dinesh Pandey , Kamal Lochan Patra

View PDF Chat

On the minimum degree of power graphs of finite nilpotent groups

2022-07-18

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

Wiener index of graphs with fixed number of pendant or cut-vertices

2022-02-28

Dinesh Pandey , Kamal Lochan Patra

View PDF Chat

On the minimum cut-sets of the power graph of a finite cyclic group

2022-01-01

Sanjay Mukherjee , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

On the super graphs and reduced super graphs of some finite groups

2022-01-01

Sandeep Dalal , Sanjay Mukherjee , Kamal Lochan Patra

For a finite group $G$, let $B$ be an equivalence (equality, conjugacy or order) relation on $G$ and let $A$ be a (power, enhanced power or commuting) graph with vertex … For a finite group $G$, let $B$ be an equivalence (equality, conjugacy or order) relation on $G$ and let $A$ be a (power, enhanced power or commuting) graph with vertex set $G$. The $B$ super $A$ graph is a simple graph with vertex set $G$ and two vertices are adjacent if either they are in the same $B$-equivalence class or there are elements in their $B$-equivalence classes that are adjacent in the original $A$ graph. The graph obtained by deleting the dominant vertices (adjacent to all other vertices) from a $B$ super $A$ graph is called the reduced $B$ super $A$ graph. In this article, for some pairs of $B$ super $A$ graphs, we characterize the finite groups for which a pair of graphs are equal. We also characterize the dominant vertices for the order super commuting graph $\Delta^o(G)$ of $G$ and prove that for $n\geq 4$ the identity element is the only dominant vertex of $\Delta^o(S_n)$ and $\Delta^o(A_n)$. We characterize the values of $n$ for which the reduced order super commuting graph $\Delta^o(S_n)^*$ of $S_n$ and the reduced order super commuting graph $\Delta^o(A_n)^*$ of $A_n$ are connected. We also prove that if $\Delta^o(S_n)^*$ (or $\Delta^o(A_n)^*$) is connected then the diameter is at most $3$ and shown that the diameter is $3$ for many value of $n.$

View PDF Chat

Some new central parts of connected graphs.

2021-10-02

Dinesh Pandey , Kamal Lochan Patra

Characterizing finite nilpotent groups associated with a graph theoretic equality

2021-09-28

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

On the number of connected subgraphs of graphs

2021-06-01

Dinesh Pandey , Kamal Lochan Patra

Characterizing finite nilpotent groups associated with a graph theoretic equality

2021-05-27

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

Some new central parts of connected graphs

2021-01-01

Dinesh Pandey , Kamal Lochan Patra

View PDF Chat

On the minimum degree of power graphs of finite nilpotent groups

2021-01-01

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

Characterizing finite nilpotent groups associated with a graph theoretic equality

2021-01-01

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

Different central parts of trees and their pairwise distances

2020-12-08

Dinesh Pandey , Kamal Lochan Patra

View PDF Chat

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

2020-10-16

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

Different central parts of trees and their pairwise distances

2020-04-05

Dinesh Pandey , Kamal Lochan Patra

Proper divisor graph of a positive integer

2020-01-01

Hitesh Kumar , Kamal Lochan Patra , Binod Kumar Sahoo

Total eccentricity index of graphs with fixed number of pendant or cut vertices

2020-01-01

Dinesh Pandey , Kamal Lochan Patra

View PDF Chat

Different central parts of trees and their pairwise distances

2020-01-01

Dinesh Pandey , Kamal Lochan Patra

A conjecture on different central parts of binary trees

2020-01-01

Dinesh Pandey , Kamal Lochan Patra

Let $\Omega_n$ be the family of binary trees on $n$ vertices obtained by identifying the root of an rgood binary tree with a vertex of maximum eccentricity of a binary … Let $\Omega_n$ be the family of binary trees on $n$ vertices obtained by identifying the root of an rgood binary tree with a vertex of maximum eccentricity of a binary caterpillar. In the paper titled "On different middle parts of a tree (The electronic journal of combinatorics, 25 (2018), no. 3, paper 3.17, 32 pp)", Smith et al. conjectured that among all binary trees on $n$ vertices the pairwise distance between any two of center, centroid and subtree core is maximized by some member of the family $\Omega_n$. We first obtain the rooted binary tree which minimizes the number of root containing subtrees and then prove this conjecture. We also obtain the binary trees which maximize these distances.

View PDF Chat

On the minimum degree of the power graph of a finite cyclic group

2019-12-18

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

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

2019-11-01

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

Laplacian eigenvalues of the zero divisor graph of the ring <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.svg"><mml:msub><mml:mrow><mml:mi mathvariant="double-struck">Z</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi></mml:mrow></mml:msub></mml:math>

2019-08-20

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

On the minimum degree of the power graph of a finite cyclic group

2019-05-26

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

Laplacian eigenvalues of the zero divisor graph of the ring $\mathbb{Z}_{n}$

2019-03-19

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

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

2019-02-08

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

Laplacian eigenvalues of the zero divisor graph of the ring $\mathbb{Z}_{n}$

2019-01-01

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

On the minimum degree of the power graph of a finite cyclic group

2019-01-01

Ramesh Prasad Panda , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

Wiener index of graphs with fixed number of pendant or cut vertices

2019-01-01

Dinesh Pandey , Kamal Lochan Patra

View PDF Chat

Maximizing distance between center, centroid and subtree core of trees

2018-12-17

Dheer Noal Desai , Kamal Lochan Patra

Extremizing the number of connected subgraphs of graphs

2018-11-28

Dinesh Pandey , Kamal Lochan Patra

The core index of a graph

2018-11-28

Dinesh Pandey , Kamal Lochan Patra

Vertex connectivity of the power graph of a finite cyclic group

2018-06-25

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

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

2018-02-21

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

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

2018-01-01

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

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

2018-01-01

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

The core index of a graph

2018-01-01

Dinesh Pandey , Kamal Lochan Patra

Bounds for the Laplacian spectral radius of graphs

2017-10-30

Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

Center, centroid and subtree core of trees

2016-12-08

Dheer Noal Desai , Kamal Lochan Patra

Minimum size blocking sets of certain line sets related to a conic in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:mi>P</mml:mi><mml:mi>G</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mi>q</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math>

2016-02-23

Kamal Lochan Patra , Binod Kumar Sahoo , Bikramaditya Sahu

Center, centroid and subtree core of trees

2016-01-01

Dheer Noal Desai , Kamal Lochan Patra

View PDF Chat

Minimizing Laplacian spectral radius of unicyclic graphs with fixed girth

2013-12-01

Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

Minimizing Laplacian spectral radius of unicyclic graphs with fixed girth

2010-12-04

Kamal Lochan Patra , Binod Kumar Sahoo

Coauthor	Papers Together
Binod Kumar Sahoo	34
Sriparna Chattopadhyay	11
Dinesh Pandey	9
Ramesh Prasad Panda	8
Sanjay Mukherjee	7
Dinesh Pandey	6
A. K. Lal	5
Sandeep Dalal	3
Dheer Noal Desai	3
Bikramaditya Sahu	1
Hiranya Kishore Dey	1
Hitesh Kumar	1
Sudip Bera	1

Undirected power graphs of semigroups

2009-01-26

Ivy Chakrabarty , Susmita Ghosh , M. K. Sen

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.

View PDF Chat

Algebraic connectivity of graphs

1973-01-01

Miroslav Fiedler

View PDF Chat

An Euler totient sum inequality

2016-01-11

Brian Curtin , Gholam Reza Pourgholi

Certain properties of the power graph associated with a finite group

2014-02-10

A. R. Moghaddamfar , S. Rahbariyan , W. J. Shi

The power graph [Formula: see text] of a group G is a simple graph whose vertex-set is G and two vertices x and y in G are adjacent if and … The power graph [Formula: see text] of a group G is a simple graph whose vertex-set is G and two vertices x and y in G are adjacent if and only if one of them is a power of the other. The subgraph [Formula: see text] of [Formula: see text] is obtained by deleting the vertex 1 (the identity element of G). In this paper, we first investigate some properties of the power graph [Formula: see text] and its subgraph [Formula: see text]. We next provide necessary and sufficient conditions for a power graph [Formula: see text] to be a strongly regular graph, a bipartite graph or a planar graph. Finally, we obtain some infinite families of finite groups G for which the power graph [Formula: see text] contains some cut-edges.

View PDF Chat

Laplacian matrices of graphs: a survey

1994-01-01

Russell Merris

Vertex connectivity of the power graph of a finite cyclic group

2018-06-25

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

Edge-maximality of power graphs of finite cyclic groups

2013-12-09

Brian Curtin , Gholam Reza Pourgholi

View PDF Chat

On connectedness of power graphs of finite groups

2017-09-18

Ramesh Prasad Panda , K. V. Krishna

The power graph of a group [Formula: see text] is the graph whose vertex set is [Formula: see text] and two distinct vertices are adjacent if one is a power … The power graph of a group [Formula: see text] is the graph whose vertex set is [Formula: see text] and two distinct vertices are adjacent if one is a power of the other. This paper investigates the minimal separating sets of power graphs of finite groups. For power graphs of finite cyclic groups, certain minimal separating sets are obtained. Consequently, a sharp upper bound for their connectivity is supplied. Further, the components of proper power graphs of [Formula: see text]-groups are studied. In particular, the number of components of that of abelian [Formula: see text]-groups are determined.

View PDF Chat

The Laplacian Spectrum of a Graph

1990-04-01

Robert Grone , Russell Merris , V. S. Sunder

Let G be a graph. The Laplacian matrix $L(G) = D(G) - A(G)$ is the difference of the diagonal matrix of vertex degrees and the 0-1 adjacency matrix. Various aspects … Let G be a graph. The Laplacian matrix $L(G) = D(G) - A(G)$ is the difference of the diagonal matrix of vertex degrees and the 0-1 adjacency matrix. Various aspects of the spectrum of $L(G)$ are investigated. Particular attention is given to multiplicities of integer eigenvalues and to the effect on the spectrum of various modifications of G.

Maximizing the distance between center, centroid and characteristic set of a tree

2007-03-30

Kamal Lochan Patra

On the power graph of a finite group

2012-01-01

Mahsa Mirzargar , Али Реза Ашрафи , M.J. Nadjafi-Arani

The power graph P(G) of a group G is the graph whose vertex set is the group elements and two elements are adjacent if one is a power of the … The power graph P(G) of a group G is the graph whose vertex set is the group elements and two elements are adjacent if one is a power of the other. In this paper, we consider some graph theoretical properties of a power graph P(G) that can be related to its group theoretical properties. As consequences of our results, simple proofs for some earlier results are presented.

View PDF Chat

Algebraic connectivity and the characteristic set of a graph

1998-12-01

R.B. Bapat , Sukanta Pati

Let Gbe a connected weighted graph on vertices {1,2,…,n} and L be the Laplacian matrix of GLet μ be the second smallest eigenvalue of L and Y be an eigenvector … Let Gbe a connected weighted graph on vertices {1,2,…,n} and L be the Laplacian matrix of GLet μ be the second smallest eigenvalue of L and Y be an eigenvector corresponding to μ. A characteristic vertex is a vertex v such that Y(v) = 0 and Y(w) ≠ 0 for some vertex w adjacent to v. An edge e with end vertices v,w is called a characteristic edge of G if Y(w) Y(v) < 0. The characteristic vertices and the characteristic edges together form the characteristic set of G. We investigate the characteristic set of an arbitrary graph. The relation between the characteristic set and nonnegative matrix theory is exploited. Bounds are obtained on the cardinality of the characteristic set. It is shown that if G is a connected graph with n vertices and m edges then the characteristic set has at most m − n + 2 elements. We use the description of the Moore-Penrose inverse of the vertex-edge incidence matrix of a tree to derive a classical result of Fiedler for a tree. Furthermore, an analogous result is obtained for an eigenvector corresponding to any eigenvalue. We obtain a formula for the Moore-Penrose inverse of the incidence matrix of a unicyclic graph and give a complete description of characteristic vectors of a unicyclic graph. It is shown that the coordinates of a characteristic vector are unimodal along the cycle in the unicyclic graph if we begin with a vertex corresponding to the smallest coordinate.

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.

View PDF Chat

Characteristic vertices of weighted trees via perron values

1996-01-01

Steve Kirkland , Michael Neumann , Bryan L. Shader

We consider a weighted tree T with algebraic connectivity μ, and characteristic vertex v. We show that μ and its associated eigenvectors can be described in terms of the Perron … We consider a weighted tree T with algebraic connectivity μ, and characteristic vertex v. We show that μ and its associated eigenvectors can be described in terms of the Perron value and vector of a nonnegative matrix which can be computed from the branches of T at v. The machinery of Perron-Frobenius theory can then be used to characterize Type I and Type II trees in terms of these Perron values, and to show that if we construct a weighted tree by taking two weighted trees and identifying a vertex of one with a vertex of the other, then any characteristic vertex of the new tree lies on the path joining the characteristic vertices of the two old trees.

Characteristic vertices of trees<sup>*</sup>

1987-12-01

Russell Merris

LetG=(V,E) be a graph with vertex set V={v 1,v 2,…vn } and edge set E. Denote by L(G) the n-by-n-matrix (aij ), where aij is the degree of vertex iwhen … LetG=(V,E) be a graph with vertex set V={v 1,v 2,…vn } and edge set E. Denote by L(G) the n-by-n-matrix (aij ), where aij is the degree of vertex iwhen j=i; aij =−1 when j≠i and {i,j}∈E; and aij =0, otherwise. While L(G) depends on the labeling of V, its characteristic polynomialqG (x) does not. The main result of the first section is a family of inequalities between the coefficients of qG (x) and the coefficients of the chromatic polynomial of G. If λ n ⩾λ n−1⩾⋯⩾λ1 are the eigenvalues of L(G), then λ1=0 and λ2>0 if and only if G is connected. For connected graphs, the eigenvectors of L(G) corresponding to λ2 afford "characteristic valuations" of G, a concept introduced by M. Fiedler. Sections II and III explore the "characteristic vertices" arising from characteristic valuations when G is a tree.

Computing the Characteristic polynomial of a graph

1974-01-01

Allen J. Schwenk

The power graph of a finite group, II

2010-01-01

Peter J‎. Cameron

The directed power graph of a group G is the digraph with vertex set G, having an arc from y to x whenever x is a power of y; the … The directed power graph of a group G is the digraph with vertex set G, having an arc from y to x whenever x is a power of y; the undirected power graph has an edge joining x and y whenever one is a power of the other. We show that, for a finite group, the undirected power graph determines the directed power graph up to isomorphism. As a consequence, two finite groups which have isomorphic undirected power graphs have the same number of elements of each order.

View PDF Chat

The full automorphism group of the power (di)graph of a finite group

2015-11-03

Min Feng , Xuanlong Ma , Kaishun Wang

View PDF Chat

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

2020-10-16

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

On the chromatic number of the power graph of a finite group

2015-04-27

Xuanlong Ma , Min Feng

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.

View PDF Chat

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

2018-01-09

Xuanlong Ma , Min Feng , Kaishun Wang

View PDF Chat

Perron components and algebraic connectivity for weighted graphs

1998-07-01

Steve Kirkland , Shaun Fallat

The algebraic connectivity of a connected graph is the second-smallest eigenvalue of its Laplacian matrix, and a remarkable result of Fiedler gives information on the structure of the eigenvectors associated … The algebraic connectivity of a connected graph is the second-smallest eigenvalue of its Laplacian matrix, and a remarkable result of Fiedler gives information on the structure of the eigenvectors associated with that eigenvalue. In this paper, we introduce the notion of a perron component at a vertex in a weighted graph, and show how the structure of the eigenvectors associated with the algebraic connectivity can be understood in terms of perron components. This leads to some strengthening of Fiedler's original result, gives some insights into weighted graphs under perturbation, and allows for a discussion of weighted graphs exhibiting tree-like structure.

The Zero-Divisor Graph of a Commutative Ring

1999-07-01

David F. Anderson , Philip S. Livingston

The power graph of a finite group

2010-03-15

Peter J‎. Cameron , Susmita Ghosh

View PDF Chat

Algebraic connectivity of trees

1987-01-01

Robert Grone , Russell Merris

View PDF Chat

Coloring of commutative rings

1988-07-01

István Beck

A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory

1975-01-01

Miroslav Fiedler

View PDF Chat

On iteration digraph and zero-divisor graph of the ring ℤ n

2014-09-01

JU Teng-xia , WU Mei-yun

View PDF Chat

Maximizing Algebraic Connectivity Over Unicyclic Graphs

2003-08-28

Shaun Fallat , Steve Kirkland , Sukanta Pati

We consider the class of unicyclic graphs on n vertices with girth g, and over that class, we attempt to determine which graph maximizes the algebraic connectivity. When g is … We consider the class of unicyclic graphs on n vertices with girth g, and over that class, we attempt to determine which graph maximizes the algebraic connectivity. When g is fixed, we show that there is an N such that for each n>N, the maximizing graph consists of a g cycle with n−g pendant vertices adjacent to a common vertex on the cycle. We also provide a bound on N. On the other hand, when g is large relative to n, we show that this graph does not maximize the algebraic connectivity, and we give a partial discussion of the nature of the maximizing graph in that situation.

Recent developments on the power graph of finite groups – a survey

2021-05-04

Ajay Kumar , Lavanya Selvaganesh , Peter J‎. Cameron +1 more

Algebraic graph theory is the study of the interplay between algebraic structures (both abstract as well as linear structures) and graph theory. Many concepts of abstract algebra have facilitated through … Algebraic graph theory is the study of the interplay between algebraic structures (both abstract as well as linear structures) and graph theory. Many concepts of abstract algebra have facilitated through the construction of graphs which are used as tools in computer science. Conversely, graph theory has also helped to characterize certain algebraic properties of abstract algebraic structures. In this survey, we highlight the rich interplay between the two topics viz groups and power graphs from groups. In the last decade, extensive contribution has been made towards the investigation of power graphs. Our main motive is to provide a complete survey on the connectedness of power graphs and proper power graphs, the Laplacian and adjacency spectrum of power graph, isomorphism, and automorphism of power graphs, characterization of power graphs in terms of groups. Apart from the survey of results, this paper also contains some new material such as the contents of Section 2 (which describes the interesting case of the power graph of the Mathieu group M11) and Section 6.1 (where conditions are discussed for the reduced power graph to be not connected). We conclude this paper by presenting a set of open problems and conjectures on power graphs.

View PDF Chat

Adjacency matrices of zero-divisor graphs of integers modulo<i>n</i>

2015-09-28

Matthew Young

Adjacency matrices of zero-divisor graphs of integers modulo n Matthew Young (Communicated by Kenneth S. Berenhaut Adjacency matrices of zero-divisor graphs of integers modulo n Matthew Young (Communicated by Kenneth S. Berenhaut

View PDF Chat

On the zero-divisor graph of a commutative ring

2003-10-14

Saieed Akbari , Abdolmajid Mohammadian

Laplacian eigenvalues of the zero divisor graph of the ring <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.svg"><mml:msub><mml:mrow><mml:mi mathvariant="double-struck">Z</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi></mml:mrow></mml:msub></mml:math>

2019-08-20

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

A survey of graph laplacians

1995-07-01

Russell Merris

Abstract Let G be a graph on n vertices. Its Laplacian is the n-by-n matrix L(G)−D(G)−A(G), where D(G) is the diagonal matrix of vertex degrees and A(G) is the (0,1)-adjacency … Abstract Let G be a graph on n vertices. Its Laplacian is the n-by-n matrix L(G)−D(G)−A(G), where D(G) is the diagonal matrix of vertex degrees and A(G) is the (0,1)-adjacency matrix of G. This article surveys recent results on graph Laplacians. 1This article was prepared in conjunction with the ICMS workshop on Algebraic Graph Theory at the University of Edinburgh, July 12 10. 1993. 1This article was prepared in conjunction with the ICMS workshop on Algebraic Graph Theory at the University of Edinburgh, July 12 10. 1993. Notes 1This article was prepared in conjunction with the ICMS workshop on Algebraic Graph Theory at the University of Edinburgh, July 12 10. 1993.

On the minimum degree, edge-connectivity and connectivity of power graphs of finite groups

2018-01-18

Ramesh Prasad Panda , K. V. Krishna

In this paper, the minimum degree of power graphs of certain cyclic groups, abelian p-groups, dihedral groups and dicyclic groups are obtained. It is ascertained that the edge-connectivity and minimum … In this paper, the minimum degree of power graphs of certain cyclic groups, abelian p-groups, dihedral groups and dicyclic groups are obtained. It is ascertained that the edge-connectivity and minimum degree of power graphs are equal, and consequently, the minimum disconnecting sets of power graphs of the aforementioned groups are determined. In order to investigate the equality of connectivity and minimum degree of power graphs, certain necessary conditions for finite groups and a necessary and sufficient condition for finite cyclic groups are obtained. Moreover, the equality is discussed for the power graphs of abelian p-groups, dihedral groups and dicyclic groups.

View PDF Chat

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

2019-02-08

Sriparna Chattopadhyay , Kamal Lochan Patra , Binod Kumar Sahoo

View PDF Chat

Coloring the Power Graph of a Semigroup

2017-02-04

Yaroslav Shitov

View PDF Chat

On the Wiener index of unicyclic graphs with given girth.

2010-01-01

Guihai Yu , Lihua Feng

On the characteristic set, centroid, and centre for a tree

2017-03-27

Nair Maria Maia de Abreu , Eliseu Fritscher , Cláudia Marcela Justel +1 more

Given a tree T, we consider a pair of vertices (u, v) where u is a centroid of T, v is a characteristic vertex of T, and such that the … Given a tree T, we consider a pair of vertices (u, v) where u is a centroid of T, v is a characteristic vertex of T, and such that the distance between them, denoted d(u, v), is smallest over all such pairs. We define and where the maximum is taken over all trees T on n vertices. Analogous definitions are also given for and . We show that for each there is a broom T on n vertices such that and a broom on n vertices such that We also prove that the sequences and are convergent, and find their limits. We rely on the characterization of characteristic vertices in terms of Perron branches in order to establish our results.

The spectral radius of triangle-free graphs

2002-01-01

Xiao‐Dong Zhang , Rong Luo

In this note, we present two lower b ounds for the spectral radius of the Laplacian matrices of triangle-free graphs. One is in terms of the numb ers of edges … In this note, we present two lower b ounds for the spectral radius of the Laplacian matrices of triangle-free graphs. One is in terms of the numb ers of edges and vertices of graphs, and the other is in terms of degrees and average 2-degrees of vertices. We also obtain some other related results.

The Laplacian Spectrum of a Graph II

1994-05-01

Robert Grone , Russell Merris

Let G be a graph. Denote by $D( G )$ the diagonal matrix of its vertex degrees and by $A( G )$ its adjacency matrix. Then $L( G ) = … Let G be a graph. Denote by $D( G )$ the diagonal matrix of its vertex degrees and by $A( G )$ its adjacency matrix. Then $L( G ) = D( G ) - A( G )$ is the Laplacian matrix of G. The first section of this paper is devoted to properties of Laplacian integral graphs, those for which the Laplacian spectrum consists entirely of integers. The second section relates the degree sequence and the Laplacian spectrum through majorization. The third section introduces the notion of a d-cluster, using it to bound the multiplicity of d in the spectrum of $L( G )$.

The Number of Subtrees of Trees with Given Degree Sequence

2012-08-06

Xiu‐Mei Zhang , Xiaodong Zhang , Daniel Gray +1 more

Abstract This article investigates some properties of the number of subtrees of a tree with given degree sequence. These results are used to characterize trees with the given degree sequence … Abstract This article investigates some properties of the number of subtrees of a tree with given degree sequence. These results are used to characterize trees with the given degree sequence that have the largest number of subtrees, which generalize the recent results of Kirk and Wang (SIAM J Discrete Math 22 (2008), 985–995). These trees coincide with those which were proven by Wang and independently Zhang et al. (2008) to minimize the Wiener index. We also provide a partial ordering of the extremal trees with different degree sequences, some extremal results follow as corollaries.

View PDF Chat

On diameter of the commuting graph of a full matrix algebra over a finite field

2015-09-18

David Dolžan , Damjana Kokol Bukovšek , Bojan Kuzma +1 more

Minimal paths in the commuting graphs of semigroups

2010-11-25

João Araújo , Michael Kinyon , Janusz Konieczny

View PDF Chat

Further Analysis on the Total Number of Subtrees of Trees

2012-12-31

Shuchao Li , Shujing Wang

When considering the total number of subtrees of trees, the extremal structures which maximize this number among binary trees and trees with a given maximum degree lead to some interesting … When considering the total number of subtrees of trees, the extremal structures which maximize this number among binary trees and trees with a given maximum degree lead to some interesting facts that correlate to some other graphical indices in applications. Along this line, it is interesting to study that over some types of trees with a given order, which trees minimize or maximize this number. Here are our main results: (1) The extremal tree which minimizes the total number of subtrees among $n$-vertex trees with $k$ pendants is characterized. (2) The extremal tree which maximizes (resp. minimizes) the total number of subtrees among $n$-vertex trees with a given bipartition is characterized. (3) The extremal tree which minimizes the total number of subtrees among the set of all $q$-ary trees with $n$ non-leaf vertices is identified. (4) The extremal $n$-vertex tree with given domination number maximizing the total number of subtrees is characterized.

View PDF Chat

Trees with the most subtrees: an algorithmic approach

2012-01-01

Daniel Gray , Hua Wang , Xiao‐Dong Zhang +1 more

When considering the number of subtrees of trees, the extremal structures which maximize this number among binary trees and trees with a given maximum degree lead to some interesting facts … When considering the number of subtrees of trees, the extremal structures which maximize this number among binary trees and trees with a given maximum degree lead to some interesting facts that correlate to other graphical indices in applications.The number of subtrees in the extremal cases constitute sequences which are of interest to number theorists.The structures which maximize or minimize the number of subtrees among general trees, binary trees and trees with a given maximum degree have been identified previously.Most recently, results of this nature are generalized to trees with a given degree sequence.In this note, we characterize the trees which maximize the number of subtrees among trees of a given order and degree sequence.Instead of using theoretical arguments, we take an algorithmic approach that explicitly describes the process of achieving an extremal tree from any random tree.The result also leads to some interesting questions and provides insight on finding the trees close to extremal and their numbers of subtrees.

View PDF Chat

The commuting graph of the symmetric inverse semigroup

2015-03-28

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

View PDF Chat

A Combinatorial Laplacian with Vertex Weights

1996-08-01

Fan Chung , R. P. Langlands

One of the classical results in graph theory is the matrix-tree theorem which asserts that the determinant of a cofactor of the combinatorial Laplacian is equal to the number of … One of the classical results in graph theory is the matrix-tree theorem which asserts that the determinant of a cofactor of the combinatorial Laplacian is equal to the number of spanning trees in a graph (see [1, 17, 11, 15]). The usual notion of the combinatorial Laplacian for a graph involves edge weights. Namely, a Laplacian L forGis a matrix with rows and columns indexed by the vertex setVofG, and the (u,v)-entry of L, foru,vinG,u≠v, is associated with the edge-weight of the edge (u,v). It is not so obvious to consider Laplacians with vertex weights (except for using some symmetric combinations of the vertex weights to define edge-weights). In this note, we consider a vertex weighted Laplacian which is motivated by a problem arising in the study of algebro-geometric aspects of the Bethe Ansatz [18]. The usual Laplacian can be regarded as a special case with all vertex-weights equal. We will generalize the matrix-tree theorem to matrix-tree theorems of counting "rooted" directed spanning trees. In addition, the characteristic polynomial of the vertex-weighted Laplacian has coefficients with similar interpretations. We also consider subgraphs with non-trial boundary. We will shown that the Laplacian with Dirichlet boundary condition has its determinant equal to the number of rooted spanning forests. The usual matrix-tree theorem is a special case with the boundary consisting of one single vertex.