Narrow Results

Bera [Line graph characterization of power graphs of finite nilpotent groups, Comm. Algebra50(11) (2022) 4652–4668] characterized finite nilpotent groups whose power graphs and proper power graphs are line graphs. In this paper, we extend the results of above-mentioned paper to arbitrary finite groups. Also, we correct the corresponding result of the proper power graphs of dihedral groups. Moreover, we classify all the finite groups whose enhanced power graphs are line graphs. We classify all the finite nilpotent groups (except non-abelian $2$-groups) whose proper enhanced power graphs are line graphs of some graphs. Finally, we determine all the finite groups whose (proper) power graphs and (proper) enhanced power graphs are the complement of line graphs, respectively.

The energy of a graph is calculated by summing the absolute values of the eigenvalues found in its adjacency matrix. In this study, we present examples of line graphs with energy equivalent to the energy of a complete graph, which are called the borderenergetic graphs. As the examples of borderenergetic line graphs are rare, we introduce a new type of graphs called almost borderenergetic graphs whose energy differs from the borderenergetic energy by at most 1. In this paper, we begin by exploring the energy properties of line graphs derived from regular graphs and strongly regular graphs. Specifically, we establish a criterion for a line graph to exhibit borderenergetic characteristics when it consists of $p$ many connected regular graphs and $q$ many complete graphs, even when the original regular graph is disconnected. Additionally, we present a criterion for the line graph of a strongly regular graph to exhibit borderenergetic characteristics. To illustrate these concepts, we offer examples of connected borderenergetic graphs that are not necessarily complete. In the second part, we give the spectrum of the line graph of $r{K}_1\nabla K_2$, and show that it is an almost borderenergetic graph for $r\ge 5$.

Let $R$ be a commutative ring with unity. The prime ideal sum graph of the ring $R$ is the simple undirected graph whose vertex set is the set of all nonzero proper ideals of $R$ and two distinct vertices $I$, $J$ are adjacent if and only if $I+J$ is a prime ideal of $R$. In this paper, we characterize all commutative Artinian rings whose prime ideal sum graphs are line graphs. Finally, we give a description of all commutative Artinian rings whose prime ideal sum graph is the complement of a line graph.

The edge version of the Nirmala index is defined in terms of edge degrees as $\mathrm{\text{EN}}(G)={\sum }_{e\sim f}\sqrt{d(e)+d(f)}$, where $d(x)$ denotes the degree of the edge $x$ in graph $G$ and $e\sim f$ means that the edges $e$ and $f$ are adjacent. In this paper, we obtain some sharp bounds for the edge version of the Nirmala index in terms of the edge version of topological indices. Also, we give the extremal unicyclic graphs of order $n$ with the minimum edge version of the Nirmala index.

Communication networks must be constructed to be as stable as possible, not only with the respect to the initial disruption, but also with respect to the possible reconstruction. Many graph theoretical parameters have been used to describe the stability of communication networks. Tenacity is a reasonable one, which shows not only the difficulty to break down the network but also the damage that has been caused. Total graphs are the largest graphs formed by the adjacent relations of elements of a graph. Thus, total graphs are highly recommended for the design of interconnection networks. In this paper, we determine the tenacity of the total graph of a path, cycle and complete bipartite graph, and thus give a lower bound of the tenacity for the total graph of a graph.

The distance dynamics model was recently proposed to detect the disjoint community of a complex network. To identify the overlapping structure of a network using the distance dynamics model, an overlapping community detection algorithm, called L-Attractor, is proposed in this paper. The process of L-Attractor mainly consists of three phases. In the first phase, L-Attractor transforms the original graph to a link graph (a new edge graph) to assure that one node has multiple distances. In the second phase, using the improved distance dynamics model, a dynamic interaction process is introduced to simulate the distance dynamics (shrink or stretch). Through the dynamic interaction process, all distances converge, and the disjoint community structure of the link graph naturally manifests itself. In the third phase, a recovery method is designed to convert the disjoint community structure of the link graph to the overlapping community structure of the original graph. Extensive experiments are conducted on the LFR benchmark networks as well as real-world networks. Based on the results, our algorithm demonstrates higher accuracy and quality than other state-of-the-art algorithms.

Local community detection algorithms are an important type of overlapping community detection methods. Local community detection methods identify local community structure through searching seeds and expansion process. In this paper, we propose a novel local community detection method on line graph through degree centrality and expansion (LCDDCE). We firstly employ line graph model to transfer edges into nodes of a new graph. Secondly, we evaluate edges relationship through a novel node similarity method on line graph. Thirdly, we introduce local community detection framework to identify local node community structure of line graph, combined with degree centrality and PageRank algorithm. Finally, we transfer them back into original graph. The experimental results on three classical benchmarks show that our LCDDCE method achieves a higher performance on normalized mutual information metric with other typical methods.

Overlapping community detection is a hot topic in the research of data mining and graph theory. In this paper, we propose a link community detection method based on ensemble learning (LCDEL). First, we transform graph into line graph and construct node adjacency matrix of line graph. Second, we calculate node distance of line graph through a new distance metric and get node distance matrix of line graph. Third, we use PCA method to reduce dimensions of node distance matrix of line graph. Then, we cluster on the reduced node distance matrix by k-means clustering algorithm. Finally, we convert line graph back into original graph and get overlapping communities of original graph with ensemble learning. Experimental results on several real-world networks demonstrate effectiveness of LCDEL method in terms of Normalized Mutual Information (NMI), Extended Modularity (EQ) and F-score evaluation metrics.

More and more attention has focused on consensus problem in the study of complex networks. Many researchers investigated consensus dynamics in a linear dynamical system with additive stochastic disturbances. In this paper, we construct iterated line graphs of multi-subdivision graph by applying multi-subdivided-line graph operation. It has been proven that the network coherence can be characterized by the Laplacian spectrum of network. We study the recursion formula of Laplacian eigenvalues of the graphs. After that, we obtain the scalings of the first- and second-order network coherence.

A signed graph is an ordered pair $S=(S^u,\sigma )$, where $S^u$ is a graph G = (V, E), called the underlying graph of S and $\sigma :E\to \{+,-\}$ is a function from the edge set E of S^u into the set {+, -}, called the signature of S. In this paper, we characterize all those signed graphs whose 2-path signed graphs are isomorphic to their square signed graph along with algorithm to check the same. In other sections we find the characterization of signed graph S such that $D_2\cong D^2$ where D is a derived signed graph of the signed graph S such as: line signed graphs, total signed graphs, common edge signed graphs, splitting signed graphs. Also each characterization is supported by algorithms for the same.

For a vertex set $M$, we say that $M$ is a monitoring-edge-geodetic set (MEG-set for short) of graph $G$, that is, some vertices of $M$ can monitor an edge of the graph, if and only if we can remove that edge would change the distance between some pair of vertices in the set. The monitoring-edge-geodetic number$meg(G)$ of a graph $G$ is defined as the minimum cardinality of a monitoring-edge-geodetic set of $G$. The line graph$L(G)$ of $G$ is the graph whose vertices are in one-to-one correspondence with the edges of $G$, that is, if two vertices are adjacent in $L(G)$ if and only if the corresponding edges have a common vertex in $G$. In this paper, we study the relation between $meg(G)$ and $meg(L(G))$, and prove that $2\le meg(L(G))\le |E(G)|$. Next, we have determined the exact values for a MEG-set of some special graphs and their line graphs. For a graph $G$ and its line graph $L(G)$, we prove that $meg(L(G))-meg(G)$ can be arbitrarily large.

The line graph is a very popular research object in graph theory, in complex networks and also in social networks recently. Let $L(K_{m,n})$ be the line graph of the complete bipartite graph $K_{m,n}$ and $P_{k+1}$ be a path of length $k$. In this paper, we give necessary and sufficient conditions for the existence of $P_4$-decompositions of $L(K_{m,n})$.

In this paper, we study the zero-divisor graph $\mathrm{\Gamma }(P)$ of a poset $P$ and its line graph $L(\mathrm{\Gamma }(P))$. We characterize all posets whose $\mathrm{\Gamma }(P)$ are star, finite complete bipartite or finite. Also, we prove that the diameter of $L(\mathrm{\Gamma }(P))$ is at most 3 while its girth is either 3, 4 or $\infty$. We also characterize $L(\mathrm{\Gamma }(P))$ in terms of their diameter and girth. Finally, we classify all posets $P$ whose $L(\mathrm{\Gamma }(P))$ are planar.

By generalizing the notion of the path ideal of a graph, we study some algebraic properties of some path ideals associated to a line graph. We show that the quotient ring of these ideals are always sequentially Cohen–Macaulay and also provide some exact formulas for the projective dimension and the regularity of these ideals. As some consequences, we give some exact formulas for the depth of these ideals.

In this paper, we study some graph-theoretic properties about the zero-divisor graph $\mathrm{\Gamma }(Q)$ of a finite quasi-ordered set $Q$ with a least element 0 and its line graph $L(\mathrm{\Gamma }(Q))$. First, we offer a method to find all the minimal prime ideals of a quasi-ordered set. Especially, this method is applicable for a partially ordered set. Then, we completely characterize the diameter and girth of $\mathrm{\Gamma }(Q)$ by the minimal prime ideals of $Q$. Besides, we perfectly classify all finite quasi-ordered sets whose zero-divisor graphs are complete graphs, star graphs, complete bipartite graphs, complete $k$-partite graphs. We also investigate the planarity of $\mathrm{\Gamma }(Q)$. Finally, we obtain the characterization for the line graph $L(\mathrm{\Gamma }(Q))$ in terms of its diameter, girth and planarity.

Let $R$ be a commutative ring and $\mathrm{\Gamma }(R)$ be the zero divisor graph of $R$. In this paper, we investigate when the zero divisor graph is a line graph. We completely present all commutative rings which their zero divisor graphs are line graphs. Also, we study when the zero divisor graph is the complement of a line graph.

Let $H$ be a simple undirected graph. The family of all matchings of $H$ forms a simplicial complex called the matching complex of $H$. Here, we give a classification of all graphs with a Gorenstein matching complex. Also we study when the matching complex of $H$ is Cohen–Macaulay and, in certain classes of graphs, we fully characterize those graphs which have a Cohen–Macaulay matching complex. In particular, we characterize when the matching complex of a graph with girth at least five or a complete graph is Cohen–Macaulay.

Bermond conjectured that if G is Hamilton cycle decomposable, then L(G), the line graph of G is Hamilton cycle decomposable. In this paper, we prove that, for any k > 5, there exists a directed Hamilton cycle decomposable 2-diregular digraph D of order 2k such that L(D) is not directed Hamilton cycle decomposable.

The minimum edge version of metric basis is the smallest set $S_E$ of edges in a connected graph $G$ such that for every pair of edges $e_1,e_2$$\in$$E_G,$ there exists an edge $e$$\in$$S_E$ for which $d_E(e_1,e)$$\ne$$d_E(e_2,e)$ holds. In this paper, the families of grid graphs and generalized prism graphs have been studied for edge version of metric dimension. Edge version of metric dimension is found to be constant for both families of graphs.

Let $G$ be a graph of the order $n$ and size $m$. The minimum edge dominating energy is defined as the sum of the absolute values of eigenvalues of the minimum edge dominating matrix of the graph $G$. In this paper, we establish relations between the minimum edge dominating energy of a graph $G$ and the graph energy, the energy of the line graph, signless Laplacian energy of $G$.