Search

Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time so that all the intermediate paths are also shortest paths. This problem has several natural applications, namely: (a) repaving road networks, (b) rerouting data packets in a synchronous multiprocessing setting, (c) the shipping container stowage problem, and (d) the train marshalling problem. When modelled as graph problems, (a) is the most general case while (b), (c), (d) are restrictions to different graph classes. We show that (a) does not admit polynomial-time algorithms (assuming P ≠ NP ), even for relaxed variants of the problem (assuming P ≠ PSPACE ). For (b), (c), (d), we present polynomial-time algorithms to solve the respective problems. We also generalize the problem to when at most k (for a fixed integer k ≥ 2 ) contiguous vertices on a shortest path can be changed at a time. [ABSTRACT FROM AUTHOR]

The vertices of a graph are to be labelled with 0 or 1 such that each edge gets the label as the product of its end vertices. If the number of vertices labelled with 0’s and 1’s differ by at most one and if the number of edges labelled with 0’s and 1’s differ by at most by one, then the labelling is called product cordial labelling. Complete characterizations of product cordial dragon graphs is given. We also characterize dragon graphs whose line graphs are product cordial. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Let m (G , λ) , c (G) and p (G) be the multiplicity of an eigenvalue λ , the cyclomatic number and the number of pendant vertices of a connected graph G , respectively. Yang et al. (2023) [10] proved that m (L (T) , λ) ≤ p (T) − 1 for any tree T , and characterized all trees T with m (L (T) , λ) = p (T) − 1 , where L (T) is the line graph of T. In this paper, we extend their result from a tree T to any graph G ≠ C n , and prove that m (L (G) , λ) ≤ 2 c (G) + p (G) − 1 for any graph G ≠ C n. Moreover, all graphs G with m (L (G) , − 1) = 2 c (G) + p (G) − 1 are completely characterized. [ABSTRACT FROM AUTHOR]

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 rK1∇K2, and show that it is an almost borderenergetic graph for r ≥ 5. [ABSTRACT FROM AUTHOR]

Background: Resting‐state functional magnetic resonance imaging (rs‐fMRI) technology and the complex network theory can be used to elucidate the underlying mechanisms of brain diseases. The successful application of functional brain hypernetworks provides new perspectives for the diagnosis and evaluation of clinical brain diseases; however, many studies have not assessed the attribute information of hyperedges and could not retain the high‐order topology of hypergraphs. In addition, the study of multi‐scale and multi‐layered organizational properties of the human brain can provide richer and more accurate data features for classification models of depression. Purpose: This work aims to establish a more accurate classification framework for the diagnosis of major depressive disorder (MDD) using the high‐order line graph algorithm. And accuracy, sensitivity, specificity, precision, F1 score are used to validate its classification performance. Methods: Based on rs‐fMRI data from 38 MDD subjects and 28 controls, we constructed a human brain hypernetwork and introduced a line graph model, followed by the construction of a high‐order line graph model. The topological properties under each order line graph were calculated to measure the classification performance of the model. Finally, intergroup features that showed significant differences under each order line graph model were fused, and a support vector machine classifier was constructed using multi‐kernel learning. The Kolmogorov–Smirnov nonparametric permutation test was used as the feature selection method and the classification performance was measured with the leave‐one‐out cross‐validation method. Results: The high‐order line graph achieved a better classification performance compared with other traditional hypernetworks (accuracy = 92.42%, sensitivity = 92.86%, specificity = 92.11%, precision = 89.66%, F1 = 91.23%). Furthermore, the brain regions found in the present study have been previously shown to be associated with the pathology of depression. Conclusions: This work validated the classification model based on the high‐order line graph, which can better express the topological features of the hypernetwork by comprehensively considering the hyperedge information under different connection strengths, thereby significantly improving the classification accuracy of MDD. Therefore, this method has potential for use in the clinical diagnosis of MDD. [ABSTRACT FROM AUTHOR]

Let X be a tree with n vertices and L (X) be its line graph. In this work, we completely characterize the trees for which the algebraic connectivity of L (X) × K m is equal to m − 1 , where × denotes the Kronecker product. We provide a few necessary and sufficient conditions for L (X) × K m to be Laplacian integral. The algebraic connectivity of L (X) × K m , where X is a tree of diameter 4 and k -book graph is discussed. [ABSTRACT FROM AUTHOR]

A class of K-metacyclic group of order p(p-1) denoted by G, has group presentation xp = yp-1 = 1; y-1xy = xr; (r - 1, p) = 1 where p is an odd prime and r is a primitive root modulo p. To this group, we attach a simple undirected graph Γcc G whose vertices are the conjugacy classes of G and two distinct vertices x and y are connected by an edge if the gcd of the class size of x and y is greater than 1. In this paper, ΓccG and ΓccG×G are obtained and then different graph theoretic properties like planarity, clique number, chromatic number, independence number, clique polynomial, independence polynomial, dominating number, spectrum and energy of these graphs are studied. The line graph of ΓccG is found to be a regular graph and the complement graph of ΓccG is found to be a star graph. Various aspects of the line graph and the complement graph are also determined in this paper. [ABSTRACT FROM AUTHOR]

Brain functional hypernetwork is widely used in the classification diagnosis of brain diseases. In the existing studies, the construction of brain functional hypernetwork is extensively studied to improve classification accuracy, but the impact of brain functional hypernetwork topology on classification performance is overlooked. However, it was showed that hyperedge information could make up for the characteristics of hypernetworks, and the transmission between hyperedges is conducive to overall learning. In view of this problem, hyperedge learning of unweighted brain hypernetwork based on line graph was proposed to analyze the influence of hyperedge on the topology and classification performance. Specifically, firstly, based on functional magnetic resonance data, the star extension method was used to construct brain functional hypernetwork. Secondly, line graph theory was introduced to construct the line graph model. Next, hyperedge density was extracted as local feature and nonparametric test was performed to select feature. Then, the graphbased substructure pattern mining algorithm was adopted to extract subgraph and the frequent score feature selection was applied to select discriminate subgraph. Finally, support vector machine was employed to construct classification model. The results show that the classification results of the proposed method are better than those of traditional brain function hypernetwork, reaching 86. 79%. It is concluded that the topological information of the brain function hypernetwork affected the construction of the classification model. In addition, the fusion features obtained based on the line graph model are better than any single type of features, reaching 88. 68% . It is suggested that that for hyperedge topology information extraction, the attribute information of the hyperedge needs to be considered, and the spatial transfer information ability between hyperedges needs to be considered. [ABSTRACT FROM AUTHOR]

Let G = (V (G), E(G)) be a graph with degree sequence ⟨d1, d2, · · ·, dn⟩, where d1 ≥ d2 ≥ · · · ≥ dn. The polynomial representation of G is given by fG(x) = Σn i=1 x di = ∆( X G) k=1 akx k, where ak is the number of vertices of G having degree k for each i = 1, 2, · · · n = ∆(G). In this paper, we give the polynomial representation of the complement and line graph of a graph, the shadow graph, complementary prism, edge corona, strong product, symmetric product, and disjunction of two graphs. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a connected graph with the vertex-set V and the edgeset E. The subdivision graph S(G) of the graph G is obtained from G by adding a vertex in the middle of every edge of G. In this paper, we investigate some properties of the graphs S (G) and L(S (G)), where L(S (G)) is the line graph of S (G). We will see that S (G) and L(S (G)) inherit some properties of G. For instance, we show that if G Cn, then Aut(G) = Aut(L(S(G))) (as abstract groups), where Cn is the cycle of order n. [ABSTRACT FROM AUTHOR]

Let G S be the graph obtained by attaching a self-loop at every vertex in S ⊆ V (G) of a simple graph G of order n. In this paper, we explore several new results related to the line graph L (G S) of G S. Particularly, we show that every eigenvalue of L (G S) must be at least - 2 , and relate the characteristic polynomial of the line graph L(G) of G with the characteristic polynomial of the line graph L (G ^) of a self-loop graph G ^ , which is obtained by attaching a self-loop at each vertex of G. Then, we provide some new bounds for the eigenvalues and energy of G S. As one of the consequences, we obtain that the energy of a connected regular complete multipartite graph is not greater than the energy of the corresponding self-loop graph. Lastly, we establish a lower bound of the spectral radius in terms of the first Zagreb index M 1 (G) and the minimum degree δ (G) , as well as proving two Nordhaus–Gaddum-type bounds for the spectral radius and the energy of G S , respectively. [ABSTRACT FROM AUTHOR]

Bera [Line graph characterization of power graphs of finite nilpotent groups, Comm. Algebra 50(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. [ABSTRACT FROM AUTHOR]

A connected graph |$G$| is called strongly Menger edge connected if |$G$| has min{deg |$_{G}(x)$|⁠ , deg |$_{G}(y)$| } edge-disjoint paths between any two distinct vertices |$x$| and |$y$| in |$G$|⁠. In this paper, we consider two types of the strongly Menger edge connectivity of the line graphs of generalized |$n$| -dimensional hypercubes with faulty edges, namely the |$m$| -edge-fault-tolerant and |$m$| -conditional edge-fault-tolerant strongly Menger edge connectivity. We show that the line graphs of all generalized |$n$| -dimensional hypercubes are |$(2n-4)$| -edge-fault-tolerant strongly Menger edge connected for |$n\geq 3$| and |$(4n-10)$| -conditional edge-fault-tolerant strongly Menger edge connected for |$n\geq 4$|⁠. The two bounds for the maximum numbers of faulty edges are best possible. [ABSTRACT FROM AUTHOR]

Topological indices are the molecular descriptors that characterize the formation of chemical compounds and predict certain physicochemical properties. Reverse degreebased topological indices play an important role in calculating topological descriptors. Line graphs illustrate the molecular graphs of chemical structures in another way and used to predict the physicochemical properties of chemical structures. In this article, we compute some reverse degree-based topological indices of the line graph of Zanamivir and Oseltamivir. This theoretical analysis may help chemists and people working in the pharmaceutical industry to predict the properties of H1N1 drugs without experimenting. [ABSTRACT FROM AUTHOR]

Let G be a finite simple graph with λ as an eigenvalue (i.e. an eigenvalue of the adjacency matrix of G), and let H be a star complement for λ in G. Motivated by a controllability condition, we say that H is a strong star complement for λ if G and H have no eigenvalue in common. We explore this concept in the context of line graphs, exceptional graphs, strongly regular graphs and graphs with a prescribed star complement. [ABSTRACT FROM AUTHOR]

Cross-lingual entity alignment (CLEA) aims to find equivalent entity pairs between knowledge graphs (KGs) in different languages. It is an important way to connect heterogeneous KGs and facilitate knowledge completion. Existing methods have found that incorporating relations into entities can effectively improve KG representation and benefit entity alignment, and these methods learn relation representation depending on entities, which cannot capture the diverse structures of relations. However, multiple relations in KG form diverse structures, such as adjacency structure and ring structure. This diversity of relation structures makes the relation representation challenging. Therefore, we propose to construct the weighted line graphs to model the diverse structures of relations and learn relation representation independently from entities. Especially, owing to the diversity of adjacency structures and ring structures, we propose to construct adjacency line graph and ring line graph, respectively, to model the structures of relations and to further improve entity representation. In addition, to alleviate the hubness problem in alignment, we introduce the optimal transport into alignment and compute the distance matrix in a different way. From a global perspective, we calculate the optimal 1-to-1 alignment bi-directionally to improve the alignment accuracy. Experimental results on two benchmark datasets show that our proposed method significantly outperforms state-of-the-art CLEA methods in both supervised and unsupervised manners. [ABSTRACT FROM AUTHOR]

For a graph G, the M-polynomial is defined to be... where mαβfi(α, β; ≥ 1) is the number of edges ab of G such that degG(a) = and degG(b) = fi; and ffi is the minimum degree and is the maximum degree of G. The physicochemical properties of chemical graphs are found by topological indices, in particular, the degree-based topological indices, which can be determined from an algebraic formula called M-polynomial. In this paper, we first compute the M-polynomial of the Dandelion graph and the line graph of Dandelion graph. Further, we derive some degree-based topological indices of these graphs from their respective M-polynomial. [ABSTRACT FROM AUTHOR]

The number of spanning trees of a graph G is called the complexity of G. It is known that the complexity of the line graph of a given graph G can be computed as the sum over all spanning trees of G of contributions which depend on various types of products of degrees of vertices of G. We interpret the contributions in terms of three types of multiplicative Zagreb indices, obtaining simple and compact expressions for the complexity of line graphs of graphs with low cyclomatic numbers. As an application, we determine the unicyclic graphs whose line graphs have the smallest and the largest complexity. [ABSTRACT FROM AUTHOR]

An attention aware edge-node exchange graph neural network (AENN) model was proposed, which used edge-node switched convolutional graph neural network method for graph encoding in a graph structured data representation framework for semi supervised classification and regression analysis.AENN is an universal graph encoding framework for embedding graph nodes and edges into a unified latent feature space.Specifically, based on the original undirected graph, the convolution between edges and nodes was continuously switched, and during the convolution process, attention mechanisms were used to assign weights to different neighbors, thereby achieving feature propagation.Experimental studies on three datasets show that the proposed method has significant performance improvements in semi-supervised classification and regression analysis compared to existing methods.

Let $(L,\wedge,\vee)$ be a lattice with a least element $0$. The annihilating-ideal graph of $L$, denoted by $\mathbb{AG}(L)$, is a graph whose vertex-set is the set of all non-trivial ideals of $L$ and, for every two distinct vertices $I$ and $J$, the vertex $I$ is adjacent to $J$ if and only if $I\wedge J=\{0\}$. In this paper, we characterize all lattices $L$ whose the graph $\mathfrak{L}(\mathbb{AG}(L))$ is toroidal.

The fixing number of a graph Γ is the minimum number of vertices that, when fixed, remove all nontrivial automorphisms from the automorphism group of Γ . This concept was extended to finite groups by Gibbons and Laison. The fixing set of a finite group G is the set of all fixing numbers of graphs whose automorphism groups are isomorphic to G. Surprisingly few fixing sets of groups have been established; only the fixing sets of abelian groups and dihedral groups are completely understood. However, the fixing sets of symmetric groups have been studied previously. In this article, we establish new elements of the fixing sets of symmetric groups by considering line graphs of complete graphs. We conclude by establishing the fixing sets of generalized quaternion groups. [ABSTRACT FROM AUTHOR]

Topological indices are numerical values related to a chemical structure that describes the correlation of chemical structure with different physical properties and chemical reactions. Glass has wide applications in architecture, tableware, optics, and optoelectronics. In this article, first, the mathematical relationship between M-polynomial and Banhatti indices such as K-Banhatti, δ-Banhatti, and hyper δ- Banhatti indices are obtained. Then using M-polynomial, Banhatti indices are obtained. [ABSTRACT FROM AUTHOR]

A topological index is a branch of chemical graph theory that is vital to analyzing the physio-chemical characteristics of chemical compound structures divided into a degree-based molecular structure such as Zagreb indices, a distance-based molecular structure such as Wiener index, and a mixed such as Gutman index. In this paper, some definitions, results, and examples of Wiener polynomial and index for subdivision graph of friendship, and bifriendship graphs, line subdivision graph of friendship, and bifriendship graphs were introduced. Moreover, we used the MATLAB program to calculate the Wiener polynomial and index of these graphs and refer to some applications. [ABSTRACT FROM AUTHOR]

A family of sets is called star‐shaped if all the members of the family have a point in common. The main aim of this paper is to provide a negative answer to the following question raised by Aisenberg et al., for the case k=2 $k=2$. Do there exist (n−2k+2) $(n-2k+2)$‐colorings of the (n,k) $(n,k)$‐Kneser graphs with more than k−1 $k-1$ many non‐star‐shaped color classes? [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with unity. Taloukolaei and Sahebi [Von Neumann regular graphs associated with rings, Discrete Math. Algorithms Appl. 10(3) (2018) 1850029, doi:10.1142/S1793830918500295] introduced the Von Neumann regular graph G V n r + (R) of a ring R whose vertices are the elements of R and two distinct vertices x and y are adjacent if and only if x + y is a Von Neumann regular element of R. In this paper, we investigate and determine some graph theoretic properties of the line graph L (G V n r + (R)) associated to G V n r + (R). We give some characterization results regarding the completeness, bipartiteness, traversability, diameter and girth. We also prove Beck's conjecture for L (G V n r + (R)). Finally we characterize rings having the planarity, the outerplanarity and also being the ring graph of the line graphs associated to Von Neumann regular graphs L (G V n r + (R)) of rings. [ABSTRACT FROM AUTHOR]

This paper introduces the forbidden subgraph conditions for Hamilton-connected graphs. If the degree sequence of the graph is (4 , 2 , 2 , 2 , 2) and it is connected, then it is called hourglass Γ 0 . For integers i ≥ 1 , the graph Z i is paw, which is obtained by attaching one of the vertices of the triangle to one of the end vertices of a path with a number of edges i. We show that every graph G is Hamilton-connected if G is a Γ 0 -free, K 1 , 3 -free, Z 14 -free, and a 3-connected graph. Moreover, we give an example to show the sharpness of a paw-type forbidden subgraph in a 3-connected, Hamilton-connected graph. Our focus on the Hamilton-connected problem can be applied to data center networks (DCNs). In the future, we will remove the forbidden subgraph families from our conclusions when building the network to obtain the optimal communication cost. Our result extends the result of Ryjáček and Vrána (Discrete Mathematics 344: 112350, 2021). [ABSTRACT FROM AUTHOR]

For an integer s ≥ 0, G is s-hamiltonian-connected if for any vertex sub-set S ⊆ V (G) with |S| ≤ s, G - S is hamiltonian-connected. Thomassen in1984 conjectured that every 4-connected line graph is hamiltonian (see [Re-flections on graph theory, J. Graph Theory 10 (1986) 309-324]), and Kuˇzel and Xiong in 2004 conjectured that every 4-connected line graph is hamil-tonian-connected (see [Z. Ryjáčk and P. Vrána, Line graphs of multigraphsand Hamilton-connectedness of claw-free graphs, J. Graph Theory 66 (2011)152-173]). In this paper we prove the following.(i) For s ≥ 3, every (s+4)-connected line graph is s-hamiltonian-connected.(ii) For s ≥ 0, every (s + 4)-connected line graph of a claw-free graph iss-hamiltonian-connected. [ABSTRACT FROM AUTHOR]

Edge degree conditions have been studied since the 1980s, mostly with regard to hamiltonicity of line graphs and the equivalent existence of dominating closed trails in their root graphs, as well as the stronger property of being supereulerian, i.e., admitting a spanning closed trail. For a graph G, let -2(G) = minfd(u) + d(v) j uv 2 E(G)g. Chen et al. conjectured that a 3-edge-connected graph G with sufficientl large order n and σ2(G) > n/9 - 2 is either supereulerian or contractible to the Petersen graph. We show that the conjecture is true when σ2(G) ≥ 2([n/15] - 1). Furthermore, we show that for an essentially k-edge-connected graph G with sufficiently large order n, the following statements hold. (i) If k = 2 and σ2(G) ≥ 2([n/8] - 1), then either L(G) is hamiltonian or G can be contracted to one of a set of six graphs which are not supereulerian; (ii) If k = 3 and σ2(G) ≥ 2([n/15]-1), then either L(G) is hamiltonian or G can be contracted to the Petersen graph. [ABSTRACT FROM AUTHOR]

We extend the notion of nonbacktracking walks from unweighted graphs to graphs whose edges have a nonnegative weight. Here the weight associated with a walk is taken to be the product over the weights along the individual edges. We give two ways to compute the associated generating function, and corresponding node centrality measures. One method works directly on the original graph and one uses a line graph construction followed by a projection. The first method is more efficient, but the second has the advantage of extending naturally to time-evolving graphs. Based on these generating functions, we define and study corresponding centrality measures. Illustrative computational results are also provided. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a simple graph such that λ1,..., λn be the eigenvalues of G. The energy of graph G is denoted by E(G) and is defined as E(G) = Σi=1n |λi|. The edge energy of G is the energy of line graph G. In this paper, we investigate the energy and edge energy for two Cayley graphs on the abelian group Zn4, namely, the Sudoku graph and the positional Sudoku graph. Also, we obtain graph energy and edge energy of the complement of these two graphs. [ABSTRACT FROM AUTHOR]

Copyright of Pamukkale University Journal of Education is the property of Pamukkale University Journal of Education and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of Telecommunications Science is the property of Beijing Xintong Media Co., Ltd. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Let G = (V,E) be a simple graph such that λ1,..., λn be the eigenvalues of G. The energy of graph G is denoted by E(G) and is defined as E(G) = Σi=1n |λi|. The edge energy of G is the energy of line graph G. In this paper, we investigate the energy and edge energy for two Cayley graphs on the abelian group Zn4, namely, the Sudoku graph and the positional Sudoku graph. Also, we obtain graph energy and edge energy of the complement of these two graphs. [ABSTRACT FROM AUTHOR]

Let (L;; _) be a lattice with a least element 0. The annihilating-ideal graph of L, denoted by AG(L), is a graph whose vertex-set is the set of all non-trivial ideals of L and, for every two distinct vertices I and J, the vertex I is adjacent to J if and only if I J = {0}. In this paper, we characterize all lattices L whose the graph L(AG(L)) is toroidal. [ABSTRACT FROM AUTHOR]

Existing graph contrastive learning methods often rely on differences in node features within subgraphs, lacking effective capture of the global structural information of the graph. To address this issue, we propose a novel graph contrastive learning method, Line Graph Contrastive Learning (LineGCL), aimed at overcoming the deficiencies in understanding the overall characteristics and topological structures of graphs found in current methods. LineGCL utilizes the characteristics of line graphs to transform the original graph into corresponding line graphs, presenting edge information in the form of node features, effectively capturing the global structural information of the graph. Additionally, LineGCL adopts a novel multi-view contrastive learning approach, characterizing the similarity and differences between the original graph and line graph comprehensively from the perspectives of node features and spectral features, further enhancing the model's understanding and learning capabilities of the global structure of graphs. Experimental results on public datasets demonstrate that LineGCL outperforms baseline models, achieving performance improvements ranging from 0.5% to 28.5%. These results validate the effectiveness and superiority of LineGCL in capturing and understanding global structural information, surpassing the limitations of baseline methods in graph contrastive learning.

Suppose that $G$ is a simple connected graph with vertex set $V(G)$ and edge set $E(G)$. A subset $S=\{s_1, s_2,\ldots , s_l \}$ of vertices of graph $G$ is called a doubly resolving set of $G$, if for any distinct vertices $u$ and $v$ in $G$ there are elements $x$ and $y$ in the set $S$ such that $d(u, x)-d(u, y)\ne d(v, x)-d(v, y)$. The minimum size of a doubly resolving set of the vertices of graph $G$ is denoted by ${\psi} (G)$. In this paper, we calculate the resolving sets of vertices with the minimum size for the line graph $L(C_n\circ{\overline{K}}_m)$ and graph $\left((C_n\circ{\overline{K}}_m)\square P_k\right)$, in which the symbols $\circ$ and $\square$ denote the Corona product and Cartesian product between two graphs, respectively. In particular, we show that if $n\geq 3$ and $m, k\geq 2$ are integers, then ${\psi}((C_n\circ{\overline{K}}_m)\square P_k )={\psi}(C_n\circ{\overline{K}}_m)+{\psi}(P_k )-1$, which gives a partial answer to the problem of characterizing graphs $G$ and $H$ satisfying the equality ${\psi}(G\square H)={\psi}(G)+{\psi}(H)-1$, which is recently posed in [K. Nie and K. Xu, The doubly metric dimension of cylinder graphs and torus graphs, Bull. Malays. Math. Sci. Soc., 46 (2023) 19 pp]. 1. IntroductionLet $G$ be a simple and connected graph with the set of vertices $V(G)$ and the set of edges $E(G)$. We denote the length of the shortest path between two vertices $u$ and $v$ in the graph $G$ by $d(u, v)$. We use $C_n$, $\overline{K_m}$ and $P_k$ to denote the cycle graph of order $n$, complement of the complete graph on $m$ vertices and the path graph of order $k$, respectively. Also, the line graph $G$ is denoted by $L(G)$, that the set of vertices of $L(G)$ are the same as the edges of the graph $G$, and two vertices are adjacent in the graph $L(G)$, if their corresponding edges in graph $G$ have a common vertex [6]. Our goal is to calculate some resolving sets depending on the line graph of the Corona product $C_{n}\circ \overline{K_{m}} $ and the Cartesian product $(C_{n}\circ \overline{K_{m}} )\square P_{k}$, so we give first some explanations about the Corona product and Cartesian product of graphs. Suppose $G$ and $H$ are two graphs with $n$ and $m$ vertices, respectively. If we consider $n$ copies of $H$ and for $i=1, 2,\cdots ,n$, all the vertices of the $i^{th}$ copy of $H$ are adjacent to the vertex $i$ of $G$, then the desired graph is called the Corona product of two graphs $G$ and $H$ and we denote it by $G\circ H$. Also, if $G$ and $H$ are two graphs, we denote the Cartesian product of these graphs by $G \square H$ or $G \times H$ and define in this way $V\left(G\square H\right)=V(G)\times V(H)$ and two vertices $(g, h)$ and $(g',h')$ in $G\square H$ are adjacent if and only if $g=g'$ and $hh'\in E(H)$ or $h=h'$ and $gg'\in E(G)$. For any ordered subset $S=\{ s_{1}, s_{2},\cdots,s_{k}\}$ of the vertices of graph $G$ and the vertex $v$ of $G$, representation the vertex $v$ with respect to the ordered set $S$ denoted by $r(v{|S)}$ and so it is $ r(v{|S)}=\left({d}\left(v, s_1\right),{d}\left(v, s_2\right),\ldots,{d}\left(v, s_k\right)\right)$. If all the vertices of the graph $G$ have distinct metric representations with respect to the ordered set $S$, then $S$ is called a resolving set of vertices of $G$. A resolving set of vertices of $G$ with the minimum size is called the metric dimension of the graph $G$ and it is represented by ${\beta }\left(G\right)$. The study of resolving set of vertices in graph theory dates back to the 1970s, and such concepts were first introduced in the articles [7,18]. The metric dimension of complete graphs, trees, paths, and the Cartesian product have been taken into consideration, also in the article [5] all graphs of order $n$ that have the metric dimension greater than or equal to $n-2$ are fully characterised. The subset $ S=\{s_{1},s_{2},\cdots,s_{l}\}$ of the vertices of graph $G$ is called a doubly resolving set for $G$, if for any distinct pair vertices $u$ and $v$ of $G$, there are the elements $x$ and $y$ of $S$, in which $d(u, x)-d(u, y)\ne d(v, x)-d(v, y)$. We denote the size of the minimum doubly resolving set in graph $G$ by ${\psi}\left(G\right) $. Concepts related to resolving sets and doubly resolving sets of graphs have been studied in the articles [4,5]. The graph $(C_5\circ \overline{K}_{3})$ and graph $L(C_{5}\circ \overline{K}_{3})$ are drawn in Figure 1. Also, the graph $(C_3\circ \overline{K}_{3})$ and graph $(C_{3}\circ \overline{K}_{3})\square P_{2}$ are drawn in Figure 2. 2. Main ResultsTheorem 2.1. If $n$ and $m$ are fixed positive integers, in which $n\geq 3$, $m\geq 2$, then the cardinality of minimum doubly resolving set of the line graph of graph $C_n\circ{\overline{K}}_m$ is $nm-n$. Theorem 2.2. If $n$, $m$ and $k$ are fixed positive integers, in which $n\geq 3$ and $m, k\geq 2$, then ${\beta }((C_n\circ{\overline{K}}_m)\square P_k )=nm-n+1.$ Theorem 2.3. If $n$, $m$ and $k$ are fixed positive integers, in which $n\geq 3$ and $m, k\geq 2$, then ${\psi }\left((C_n\circ \overline{K}_{m})\square P_{k}\right)={\psi } (C_n\circ \overline{K}_{m})+{\psi }(P_{k})-1.$ 3. ConclusionsConsidering the importance of the minimum resolving sets in graphs, in this paper, we first calculated some resolving sets of vertices with the minimum size for the line graph of graph $C_n\circ{\overline{K}}_m$ and graph $\left((C_n\circ{\overline{K}}_m)\square P_k\right)$. In particular, we show that if $n\geq 3$ and $m, k\geq 2$ are integers, then ${\psi}((C_n\circ{\overline{K}}_m)\square P_k )={\psi}(C_n\circ{\overline{K}}_m)+{\psi}(P_k )-1$, which gives a partial answer to the problem of characterizing graphs $G$ and $H$ satisfying the equality ${\psi}(G\square H)={\psi}(G)+{\psi}(H)-1$, which is recently posed in [15].

For a real number α\alpha , the general Randić index of a graph GG, denoted by Rα(G){R}_{\alpha }\left(G), is defined as the sum of (d(u)d(v))α{\left(d\left(u)d\left(v))}^{\alpha } for all edges uvuv of GG, where d(u)d\left(u) denotes the degree of a vertex uu in GG. In particular, R−12(G){R}_{-\tfrac{1}{2}}\left(G) is the ordinary Randić index, and is simply denoted by R(G)R\left(G). Let α\alpha be a real number. In this article, we show that (1)if α≥0\alpha \ge 0, Rα(L(G))≥2Rα(G){R}_{\alpha }\left(L\left(G))\ge 2{R}_{\alpha }\left(G) for any graph GG with δ(G)≥3\delta \left(G)\ge 3;(2)if α≥0\alpha \ge 0, Rα(L(G))≥Rα(G){R}_{\alpha }\left(L\left(G))\ge {R}_{\alpha }\left(G) for any connected graph GG which is not isomorphic to Pn{P}_{n};(3)if α

The degree-based topological indices are numerical graph invariants that are used to link a molecule’s structural characteristics to its physical, and chemical characteristics. In the investigation, and study of the structural features of a chemical network, it has emerged as one of the most potent mathematical techniques. In this paper, we study the degree-based topological invariants, called K-Banhatti indices, of the line graphs of some rooted product graphs namely, [Formula: see text], [Formula: see text], and ith vertex rooted product graph [Formula: see text] which are derived by the concept of subdivision.

Abstract In the study of the Quantitative Structure-Activity Relationship (QSAR) model, the topological index of a molecular structure as a molecular descriptor is used to analyze their molecular characteristics. Theoretical evaluation of the drug’s molecular structure helps to accelerate the process of design and discovery of drugs by understanding its mechanism of action. In this paper, we study the molecular structure of antiviral drugs, namely, Ritonavir and Lopinavir using the graph theory and the edge-partition approach. We determine the exact formula of some new Sombor-type topological indices and Sombor-type topological coindices of the molecular graph and line graph of the chemical structures of the antiviral drugs Ritonavir and Lopinavir. In this study, we apply Matlab and Mathematica software to evaluate the results and accuracy of calculations. The linear regression approach in the quantitative structure-property relationships model is used to investigate the relationships between Sombor indices and coindices and physicochemical properties. [ABSTRACT FROM AUTHOR]

The energy of a graph is defined as the sum of absolute values of all eigenvalues of its adjacency matrix. For a nonempty graph G , S. Akbari, A. Alazemi, M. Andelić and M.A. Hosseinzadeh proposed a conjecture: The energy of the line graph of G is at least | E (G) | + Δ (G) − 3 , where E (G) is the edge set of G and Δ (G) is the maximum degree of G. In this paper, we give a proof confirming the conjecture, and present a lower bound and an upper bound for the energy of line graphs of regular graphs. [ABSTRACT FROM AUTHOR]

In this paper, firstly, we will give a formula for the spectrum of a line graph of a circulant graph. Secondly, a formula for the spectrum of a line graph of a Cayley graph over an abelian group will be given. [ABSTRACT FROM AUTHOR]