9,229 results on '"Line graph"'
Search Results
2. Reconfiguring Shortest Paths in Graphs.
- Author
-
Gajjar, Kshitij, Jha, Agastya Vibhuti, Kumar, Manish, and Lahiri, Abhiruk
- Subjects
- *
POLYNOMIAL time algorithms , *SHIPPING containers , *DATA packeting , *CONTAINER ships , *PROBLEM solving - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
3. Characterization of product cordial dragon graphs.
- Author
-
Acharya, Mukti and Kureethara, Joseph Varghese
- Subjects
- *
GRAPH theory , *GEOMETRIC vertices , *EDGES (Geometry) , *MATHEMATICAL formulas , *MATHEMATICAL models - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
4. On rings whose prime ideal sum graphs are line graphs.
- Author
-
Mathil, Praveen and Kumar, Jitender
- Subjects
- *
PRIME ideals , *COMMUTATIVE rings , *LOCAL rings (Algebra) , *UNDIRECTED graphs - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
5. Realizability problem of distance-edge-monitoring numbers.
- Author
-
Ji, Zhen, Mao, Yaping, Cheng, Eddie, and Zhang, Xiaoyan
- Subjects
TREE graphs ,COMPLETE graphs ,TIMBERLINE ,INTEGERS ,FRIENDSHIP ,BIPARTITE graphs - Abstract
Let G be a graph with vertex set V (G) and edge set E(G). For a set M of vertices and an edge e of a graph G, let P (M, e) be the set of pairs (x, y) with a vertex x of M and a vertex y of V (G) such that d
G (x, y) ≠dG−e (x, y). Given a vertex x, an edge e is said to be monitored by x if there exists a vertex v in G such that (x, v) ∈P ({x}, e), and the collection of such edges is EM(x). A set M of vertices of a graph G is distance-edge-monitoring (DEM for short) set if every edge e of G is monitored by some vertex of M, that is, the set P (M, e) is nonempty. The DEM number dem(G) of a graph G is defined as the smallest size of such a set in G. The vertices of M represent distance probes in a network modeled by G; when the edge e fails, the distance from x to y increases, and thus we are able to detect the failure. In this paper, we first give some bounds or exact values of line graphs of trees, grids, complete bipartite graphs, and obtain the exact values of DEM numbers for some graphs and their line graphs, including the friendship and wheel graphs. Next, for each n, m > 1, we obtain that there exists a graph Gn,m such that dem(Gn,m ) = n and dem(L(Gn,m )) = 4 or 2n + t, for each integer t≥ 0. In the end, the DEM number for the line graph of a small-world network (DURT) is given. [ABSTRACT FROM AUTHOR]- Published
- 2024
- Full Text
- View/download PDF
6. Arbitrarily edge-partitionable graphs.
- Author
-
Bensmail, Julien
- Abstract
In this work, we introduce and study the notion of arbitrarily edge-partitionable (AEP) graphs, as an edge version of arbitrarily partitionable (AP) graphs. A graph G with order n is AP if, for every partition (λ 1 , ... , λ p) of n , there is a partition (V 1 , ... , V p) of V (G) where G [ V i ] is a connected graph with order λ i , for every i ∈ { 1 , ... , p }. Likewise, a graph G with size m is AEP if, for every partition (λ 1 , ... , λ p) of m , there is a partition (E 1 , ... , E p) of E (G) where G [ E i ] is a connected graph with size λ i , for every i ∈ { 1 , ... , p }. We here mostly investigate how the most influential results on AP graphs adapt (or not) to AEP graphs. In particular, aspects we cover include connectivity properties, connections with Hamiltonian and traceable graphs, minimality notions, and (positive and negative) algorithmic results. One additional motivation behind our results, is that a graph is AEP if and only if its line graph is AP; therefore, our investigations can also be perceived as a way to study the AP property in the context of particular classes of line graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2025
- Full Text
- View/download PDF
7. The eigenvalue multiplicity of line graphs.
- Author
-
Chang, Sarula, Li, Jianxi, and Zheng, Yirong
- Subjects
- *
GRAPH connectivity , *EIGENVALUES , *MULTIPLICITY (Mathematics) , *TREES - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
8. On the Monitoring-Edge-Geodetic Numbers of Line Graphs.
- Author
-
Bao, Gemaji, Yang, Chenxu, Ma, Zhiqiang, Ji, Zhen, Xu, Xin, and Qin, Peiyao
- Abstract
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 ≤ meg (L (G)) ≤ | 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. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
9. Almost borderenergetic line graphs.
- Author
-
Dede, Cahit and Maden, Ayşe Dilek
- Subjects
- *
GRAPH connectivity , *ABSOLUTE value , *EIGENVALUES - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
10. High‐Order line graphs of fMRI data in major depressive disorder.
- Author
-
Guo, Hao, Huang, Xiaoyan, Wang, Chunyan, Wang, Hao, Bai, Xiaohe, and Li, Yao
- Subjects
- *
FUNCTIONAL magnetic resonance imaging , *BRAIN diseases , *MENTAL depression , *GRAPH algorithms , *FEATURE selection - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
11. Algebraic connectivity of Kronecker products of line graphs.
- Author
-
Chauhan, Shivani and Reddy, A. Satyanarayana
- Subjects
- *
KRONECKER products , *PRODUCT lines , *LAPLACIAN matrices , *DIAMETER - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
12. CONJUGACY CLASS GRAPHS OF SOME K-METACYCLIC GROUPS.
- Author
-
Yangertola and Patra, Kuntala
- Subjects
CONJUGACY classes ,UNDIRECTED graphs ,CLASS size ,POLYNOMIALS - Abstract
A class of K-metacyclic group of order p(p-1) denoted by G, has group presentation x
p = yp-1 = 1; y-1 xy = 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, Γcc G and Γcc G×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 Γcc G is found to be a regular graph and the complement graph of Γcc G 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]- Published
- 2024
- Full Text
- View/download PDF
13. 基于线图的无权脑超网络超边学习及融合特征分类.
- Author
-
上官学奎, 黄晓妍, 王春燕, and 郭浩
- Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
14. Polynomial Representations and Degree Sequences of Graphs Resulting From Some Graph Operations.
- Author
-
Cruz, Jayhan, Malacas, Gina, and Canoy Jr., Sergio R.
- Subjects
- *
REPRESENTATIONS of graphs , *POLYNOMIALS , *PRISMS - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
15. Some algebraic properties of the subdivision graph of a graph.
- Author
-
Mirafzal, S. Morteza
- Subjects
- *
GRAPH theory , *GEOMETRIC vertices , *AUTOMORPHISM groups , *HAMILTONIAN graph theory , *SET theory - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
16. Line Graphs and Nordhaus–Gaddum-Type Bounds for Self-Loop Graphs.
- Author
-
Akbari, Saieed, Jovanović, Irena M., and Lim, Johnny
- Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
17. On finite groups whose power graphs are line graphs.
- Author
-
Parveen and Kumar, Jitender
- Abstract
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]- Published
- 2024
- Full Text
- View/download PDF
18. Menger-Type Connectivity of Line Graphs of Generalized Hypercubes With Faulty Edges.
- Author
-
Jia, Huanshen and Qian, Jianguo
- Subjects
- *
GRAPH connectivity , *FAULT-tolerant computing , *HYPERCUBES , *COMPUTER security , *INTERNETWORKING devices - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
19. Topological Study of Line Graph of Zanamivir and Oseltamivir Used in the Treatment of H1N1.
- Author
-
Nagesh, H. M. and Kumar, M. C. Mahesh
- Abstract
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]
- Published
- 2024
20. Modeling functional connectivity changes during an auditory language task using line graph neural networks
- Author
-
Stein Acker, Jinqing Liang, Ninet Sinaii, Kristen Wingert, Atsuko Kurosu, Sunder Rajan, Sara Inati, William H. Theodore, and Nadia Biassou
- Subjects
graph theory ,graph neural network ,line graph ,functional connectivity ,machine learning ,functional MRI ,Neurosciences. Biological psychiatry. Neuropsychiatry ,RC321-571 - Abstract
Functional connectivity (FC) refers to the activation correlation between different brain regions. FC networks as typically represented as graphs with brain regions of interest (ROIs) as nodes and functional correlation as edges. Graph neural networks (GNNs) are machine learning architectures used to analyze FC graphs. However, traditional GNNs are limited in their ability to characterize FC edge attributes because they typically emphasize the importance of ROI node-based brain activation data. Line GNNs convert the edges of the original graph to nodes in the transformed graph, thereby emphasizing the FC between brain regions. We hypothesize that line GNNs will outperform traditional GNNs in FC applications. We investigated the performance of two common GNN architectures (GraphSAGE and GCN) trained on line and traditional graphs predicting task-associated FC changes across two datasets. The first dataset was from the Human Connectome Project (HCP) with 205 participants, the second was a dataset with 12 participants. The HCP dataset detailed FC changes in participants during a story-listening task, while the second dataset included the FC changes in a different auditory language task. Our findings from the HCP dataset indicated that line GNNs achieved lower mean squared error compared to traditional GNNs, with the line GraphSAGE model outperforming the traditional GraphSAGE by 18% (p
- Published
- 2024
- Full Text
- View/download PDF
21. Exploratory Data Analysis
- Author
-
Monsen, Karen A. and Monsen, Karen A.
- Published
- 2024
- Full Text
- View/download PDF
22. StrucTemp-GNN: An Intrusion Detection Framework in IoT Networks Using Dynamic Heterogeneous Graph Neural Networks
- Author
-
Boukari, Imed Eddine, Derdouha, Ihab Abderrahmane, Bouzefrane, Samia, Hamdad, Leila, Nait-Bahloul, Safia, Huraux, Thomas, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bouzefrane, Samia, editor, Banerjee, Soumya, editor, Mourlin, Fabrice, editor, Boumerdassi, Selma, editor, and Renault, Éric, editor
- Published
- 2024
- Full Text
- View/download PDF
23. A Representation Learning Link Prediction Approach Using Line Graph Neural Networks
- Author
-
Tai, Yu, Yang, Hongwei, He, Hui, Wu, Xinglong, Zhang, Weizhe, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Liu, Qingshan, editor, Wang, Hanzi, editor, Ma, Zhanyu, editor, Zheng, Weishi, editor, Zha, Hongbin, editor, Chen, Xilin, editor, Wang, Liang, editor, and Ji, Rongrong, editor
- Published
- 2024
- Full Text
- View/download PDF
24. Demonstrating b-coloring of generalized Jahangir graphs for representing complex manufacturing process
- Author
-
Foram Chandarana, Minal. S. Shukla, Amit Sata, Ram Subbiah, Saurav Dixit, and Rajesh Mahadeva
- Subjects
b-Coloring ,b-continuity ,b-spectrum ,generalized Jahangir graph ,line graph ,investment casting ,Engineering (General). Civil engineering (General) ,TA1-2040 - Abstract
A graph’s b-coloring admits proper coloring and has the extra characteristic of having a dominating node in each color-class in the graph. [Formula: see text] the b-chromatic number, is the largest integer k for which G can be colored with k colors using the b-coloring method. G is said to be b-continuous if b-coloring exists for [Formula: see text] meeting the inequality [Formula: see text] The b-spectrum [Formula: see text] of a graph G is the set of all integers k for which a b-coloring of G exists using k colors. b-Chromatic number, b-continuity and b-spectrum of generalized Jahangir graphs and that of line graph of generalized Jahangir graphs are determined in this work and the concept of b-coloring of the generalized Jahangir graph has also been extended to represent complex manufacturing processes to enhance visualization. Investment casting is a highly complex manufacturing process widely accepted for manufacturing high-valued metallic components. The concept of b-coloring has been employed to represent investment casting. This has created a great platform to combine the approach of graph theory with a complex manufacturing process, which can be explored to perform various tasks associated with scheduling and optimization in future work.
- Published
- 2024
- Full Text
- View/download PDF
25. Strong star complements in graphs.
- Author
-
Anđelić, Milica, Rowlinson, Peter, and Stanić, Zoran
- Subjects
- *
REGULAR graphs , *EIGENVALUES - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
26. Diverse Structure-Aware Relation Representation in Cross-Lingual Entity Alignment.
- Author
-
Zhang, Yuhong, Wu, Jianqing, Yu, Kui, and Wu, Xindong
- Subjects
KNOWLEDGE graphs ,WEIGHTED graphs - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
27. On the M-polynomial and Degree-Based Topological Indices of Dandelion Graph.
- Author
-
Nagesh, H. M. and Kumar, M. C. Mahesh
- Subjects
- *
MOLECULAR connectivity index , *DANDELIONS , *MOLECULAR graphs , *CHEMICAL properties - Abstract
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]
- Published
- 2024
28. Multiplicative Zagreb Indices and Extremal Complexity of Line Graphs.
- Author
-
Došlić, Tomislav
- Subjects
GRAPH grammars ,SPANNING trees ,INDEXES ,COMBINATORICS ,MATHEMATICAL analysis - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
29. Attention aware edge-node exchange graph neural network
- Author
-
Ruiqin WANG, Yimin HUANG, Qishun JI, Chaoyi WAN, and Zhifeng ZHOU
- Subjects
graph neural network ,message passing ,attention mechanism ,hypergraph ,line graph ,Telecommunication ,TK5101-6720 ,Technology - Abstract
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.
- Published
- 2024
- Full Text
- View/download PDF
30. Atom-bond sum-connectivity index of line graphs
- Author
-
Yanyan Ge, Zhen Lin, and Jiajia Wang
- Subjects
atom-bond sum-connectivity index ,line graph ,extremal graph ,Mathematics ,QA1-939 - Published
- 2023
- Full Text
- View/download PDF
31. Line graphs associated to annihilating-ideal graph attached to lattices of genus one
- Author
-
Atossa Parsapour and Khadijeh AhmadJavaheri
- Subjects
annihilating-ideal graph ,genus ,lattice ,line graph ,toroidal graph ,Mathematics ,QA1-939 - Abstract
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.
- Published
- 2023
- Full Text
- View/download PDF
32. A generalization of quantum pair state transfer
- Author
-
Kim, Sooyeong, Monterde, Hermie, Ahmadi, Bahman, Chan, Ada, Kirkland, Stephen, and Plosker, Sarah
- Published
- 2024
- Full Text
- View/download PDF
33. Fixing Numbers of Graphs with Symmetric and Generalized Quaternion Symmetry Groups.
- Author
-
Graves, Christina and Lauderdale, L.-K.
- Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
34. Investigating Banhatti indices on the molecular graph and the line graph of Glass with M-polynomial approach.
- Author
-
Tousi, Jaber Ramezani and Ghods, Masoud
- Subjects
- *
MOLECULAR graphs , *MOLECULAR connectivity index , *CHEMICAL properties , *CHEMICAL reactions , *CHEMICAL structure , *GLASS - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
35. Computation of wiener polynomial and index of line subdivision friendship and line subdivision bifriendship graphs using matlab program.
- Author
-
Al-Rumaima, Mahmoud, Alameri, Abdu, Alsharafi, Mohammed, Saeed, Walid A. M., Ahmed, Hanan, and Alwardi, Anwar
- Subjects
- *
BILEVEL programming , *MOLECULAR connectivity index , *FRIENDSHIP , *GRAPH theory , *CHEMICAL structure , *MOLECULAR graphs , *MOLECULAR structure , *POLYNOMIALS - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
36. On the number of star‐shaped classes in optimal colorings of Kneser graphs.
- Author
-
Daneshpajouh, Hamid Reza
- Subjects
- *
GRAPH coloring - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
37. Line graphs associated to Von Neumann regular graphs of rings.
- Author
-
Boro, Laithun and Singh, Madan Mohan
- Subjects
- *
VON Neumann regular rings , *REGULAR graphs , *COMMUTATIVE rings , *PLANAR graphs - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
38. Paw-Type Characterization of Hourglass-Free Hamilton-Connected Graphs.
- Author
-
Wang, Panpan and Xiong, Liming
- Subjects
- *
COMPUTATIONAL mathematics , *TRIANGLES , *SERVER farms (Computer network management) , *FOOT , *INTEGERS - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
39. ON s-HAMILTONIAN-CONNECTED LINE GRAPHS.
- Author
-
XIAOLING MA, HONG-JIAN LAI, MINGQUAN ZHAN, TAOYE ZHANG, and JU ZHOU
- Subjects
- *
GRAPH theory , *HAMILTONIAN graph theory , *INTEGERS - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
40. EDGE DEGREE CONDITIONS FOR DOMINATING AND SPANNING CLOSED TRAILS.
- Author
-
TAO TIAN, BROERSMA, HAJO, and LIMING XIONG
- Subjects
- *
PETERSEN graphs , *HAMILTONIAN graph theory , *SPANNING trees , *LOGICAL prediction - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
41. WEIGHTED ENUMERATION OF NONBACKTRACKING WALKS ON WEIGHTED GRAPHS.
- Author
-
ARRIGO, FRANCESCA, HIGHAM, DESMOND J., NOFERINI, VANNI, and WOOD, RYAN
- Subjects
- *
GENERATING functions , *TIME-varying networks , *MATRIX functions - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
42. The energy and edge energy of some Cayley graphs on the abelian group Zn4.
- Author
-
Movahedi, Fateme
- Subjects
- *
CAYLEY graphs , *ABELIAN groups , *EIGENVALUES , *GRAPH theory , *GROUP theory - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
43. Kuvvet ve Hareket Konusuna Yönelik Lise Öğrencilerinin Grafik Çizme Düzeylerinin İncelenmesi.
- Author
-
ATAR, Betül Şeyma YELTEKİN and AYKUTLU, Işıl
- Subjects
HIGH school students - Abstract
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.)
- Published
- 2024
- Full Text
- View/download PDF
44. The energy and edge energy of some Cayley graphs on the abelian group Zn4.
- Author
-
Movahedi, Fateme
- Subjects
CAYLEY graphs ,ABELIAN groups ,EIGENVALUES ,GRAPH theory ,GROUP theory - Abstract
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=1 n |λ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 Zn 4 , 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]- Published
- 2024
- Full Text
- View/download PDF
45. 注意力感知的边-节点交换图神经网络模型.
- Author
-
王瑞琴, 黄熠旻, 纪其顺, 万超艺, and 周志峰
- Abstract
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.)
- Published
- 2024
- Full Text
- View/download PDF
46. LINE GRAPHS ASSOCIATED TO ANNIHILATING-IDEAL GRAPH ATTACHED TO LATTICES OF GENUS ONE.
- Author
-
PARSAPOUR, ATOSSA and JAVAHERI, KHADIJEH AHMAD
- Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
47. Line graph contrastive learning for node classification
- Author
-
Mingyuan Li, Lei Meng, Zhonglin Ye, Yuzhi Xiao, Shujuan Cao, and Haixing Zhao
- Subjects
Graph contrastive learning ,Line graph ,Spectral features ,Multi-angle contrast loss ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
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.
- Published
- 2024
- Full Text
- View/download PDF
48. Resolving sets of vertices with the minimum size in graphs
- Author
-
Ali Zafari, Nader Habibi, and Saeid Alikhani
- Subjects
doubly resolving set ,cartesian product ,corona product ,line graph ,Mathematics ,QA1-939 ,History of education ,LA5-2396 - Abstract
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].
- Published
- 2023
- Full Text
- View/download PDF
49. Heterogeneous Line Graph Neural Network for Link Prediction
- Author
-
Sun, Yiyang, Zhao, Yuncong, Li, Longjie, Dong, Hu, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Yang, Xiaochun, editor, Suhartanto, Heru, editor, Wang, Guoren, editor, Wang, Bin, editor, Jiang, Jing, editor, Li, Bing, editor, Zhu, Huaijie, editor, and Cui, Ningning, editor
- Published
- 2023
- Full Text
- View/download PDF
50. Nullity of Graphs—A Survey and Some New Results
- Author
-
Arumugam, S., Arathi Bhat, K., Gutman, Ivan, Karantha, Manjunatha Prasad, Poojary, Raksha, Bhatt, Abhay G., Editor-in-Chief, Basu, Ayanendranath, Editor-in-Chief, Bhat, B. V. Rajarama, Editor-in-Chief, Chattopadhyay, Joydeb, Editor-in-Chief, Ponnusamy, S., Editor-in-Chief, Chaudhuri, Arijit, Associate Editor, Ghosh, Ashish, Associate Editor, Biswas, Atanu, Associate Editor, Daya Sagar, B. S., Associate Editor, Sury, B., Associate Editor, Raja, C. R. E., Associate Editor, Delampady, Mohan, Associate Editor, Sen, Rituparna, Associate Editor, Neogy, S. K., Associate Editor, Rao, T. S. S. R. K., Associate Editor, Bapat, Ravindra B., editor, Karantha, Manjunatha Prasad, editor, Kirkland, Stephen J., editor, Neogy, Samir Kumar, editor, Pati, Sukanta, editor, and Puntanen, Simo, editor
- Published
- 2023
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.