Search

We have introduced a new continuous-time network evolution model. We have described cooperation, so we have considered the cliques of nodes. The evolution of the network was based on cliques of nodes of the network and was governed by a branching process. The basic properties of the evolution process were described. Asymptotic theorems were proved for the number of cliques having a fixed size and the degree of a fixed node. The generating function was calculated, and then the probability of extinction was obtained. For the proof, advanced results of multi-type branching processes were used. Besides precise mathematical proofs, simulation examples also supported our results.

Duan, Ning, Peng, Wang and Yang determined the maximum number of s -cliques of a graph with given minimum degree and matching number. In this note, we prove a stability version of their theorem. Namely, we prove that if the number of s -cliques in a graph G is close to the above maximum number from their theorem, then G must be a subgraph of some well-specified graphs. [ABSTRACT FROM AUTHOR]

Let R be a finite commutative ring with nonzero identity. An ideal I of R is called nilpotent of index 2 if I 2 = 0. R is called local nilpotent of index 2 if it has a unique maximal nilpotent ideal of index 2. In this paper, we investigate the interplay between cliques in the zero divisor graph and nilpotent ideals of index 2 in R. In particular, if Ω is a maximal clique and Ω ∪ { 0 } is an ideal, then Ω ∪ { 0 } is a maximal nilpotent ideal of index 2. Also, we study local nilpotent rings of index 2. Finally, we prove that every local ring of order p n with n ≤ 3 is local nilpotent of index 2 and present a counter example for p 4 . [ABSTRACT FROM AUTHOR]

The Turán number of a given graph H, denoted by ex(n, H), is the maximum number of edges in an H-free graph on n vertices. Applying a well-known result of Hajnal and Szemerédi, we determine the Turán number ex(n, Kp ∪ Kq) of a vertex-disjoint union of cliques Kp and Kq for all values of n. [ABSTRACT FROM AUTHOR]

Let n = 2 s p 1 α 1 ⋯ p k α k , where s = 0 or 1, α i ≥ 1 , and the distinct primes p i satisfy p i ≡ 1 (mod 4) for all i = 1 , … , k . Let Z n ∗ denote the group of units in the commutative ring Z n . In a recent paper, we defined the Paley-type graph G n of order n as the graph whose vertex set is Z n and xy is an edge if x - y ≡ a 2 (mod n) for some a ∈ Z n ∗ . Computing the number of cliques of a particular order in a Paley graph or its generalizations has been of considerable interest. In our recent paper, for primes p ≡ 1 (mod 4) and α ≥ 1 , by evaluating certain character sums, we found the number of cliques of order 3 in G p α and expressed the number of cliques of order 4 in G p α in terms of Jacobi sums. In this article we give combinatorial proofs and find the number of cliques of orders 3 and 4 in G n for all n for which the graph is defined. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Central China Normal University is the property of Huazhong Normal University 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.)

Mantel Theorem and Turán Theorem are fundamental results in extremal graph theory. In this note, we present short proofs of these two theorems. Our proof shows that we essentially can reduce the proof of Turán Theorem to the minimum degree condition for cliques. [ABSTRACT FROM AUTHOR]

Given an edge-coloring of a graph G, G is said to be rainbow if any two edges of G receive different colors. The anti-Ramsey number AR(G, H) is defined to be the maximum integer k such that there exists a k-edgecoloring of G avoiding rainbow copies of H. The anti-Ramsey number for graphs, especially matchings, have been studied in several graph classes. Gilboa and Roditty focused on the anti-Ramsey number of graphs with small components, especially including a matching. In this paper, we continue the work in this direct and determine the exact value of the anti-Ramsey number of K4 ∪ tP2 in complete graphs. Also, we improve the bound and obtain the exact value of AR(Kn, C3 ∪ tP2) for all n ≥ 2t + 3. [ABSTRACT FROM AUTHOR]

A graph is well-covered if all of its maximal independent sets have the same size. A graph that remains well-covered upon the removal of any vertex is called a 1-well-covered graph. These graphs, when they have no isolated vertices, are also known asW2 graphs. It is well-known that every graph G W2 has two disjoint maximum independent sets. In this paper, we investigate connected W2 graphs with n vertices that contain a clique of size n/3. We prove that if the removal of two disjoint maximum independent sets from a graph G W2 leaves a clique of size at least 3, then G contains a clique of size n/3. Using this result, we provide a complete characterization of these graphs, based on eleven graph families. [ABSTRACT FROM AUTHOR]

This article explores the concept of the power serieswise Armendariz graph of a commutative ring, denoted as PA(R). It discusses various properties of PA(R), including diameter, clique, and girth, and examines the relationship between the ring-theoretic properties of R and the graph-theoretic properties of PA(R). The article provides examples and proofs to support its findings. It also discusses the relationship between PA(R) and the graph of the ring R[[X]], denoted as Γ(R[[X]]), and establishes several equivalences between different statements about the graph. The article concludes by discussing the implications of these equivalences and providing a list of references for further reading. [Extracted from the article]

For a commutative ring R , even elements in R as vertices and two distinct vertices x i , y j ∈ R are adjacent iff x i y j = 0 or y j x i = 0 , then the graph is known as an even prime graph. In compressed even prime graph, whose vertex set is the set of all equivalence classes of even elements in R , the equivalence classes elements are denoted by [ β ] or β ¯ and two distinct equivalence classes [ β i ] and [ β j ] are adjacent iff [ β i ] [ β j ] = 0 , graph is denoted by E P G E (Z n) . This paper delves into discussions regarding the chromatic number and clique number of such graphs across various families. Additionally, we discuss the chromatic number of the prime graph associated with the commutative ring R . [ABSTRACT FROM AUTHOR]

Let R be a ring with unity and M a left R-module. We investigate a new graph associated with M called the simple-intersection graph of M, denoted by G S R (M) . Our focus is on exploring the relationship between different algebraic properties of M and properties G S R (M) , including connectedness, girth and dominating sets. Our results encompass determining the girth and diameter of GSR(M) and providing insights on the clique and domination numbers. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a c-prime fuzzy graph of a nearring with respect to a level ideal of a fuzzy ideal. We find a relation between properties of the fuzzy ideal and properties of the fuzzy graph. We introduce ideal symmetry of the fuzzy graph and obtain conditions under which the graph is ideal symmetric. We find a relation between nearring homomorphisms and graph homomorphisms. We investigate conditions required for the homomorphic image of a c-prime fuzzy ideal to be a c-prime fuzzy ideal. [ABSTRACT FROM AUTHOR]

Let Dn be dihedral group of order 2n with identity element e then its square power graph is a undirected, finite, simple graph in which pair of distinct vertices a, b have edge iff ab = c² or ba = c² for any c ∈ Dn where c² = e. In this research paper we have studied various structural properties such as connectedness, vertex degree, girth, clique, chromatic number and laplacian spectrum of square power graph of dihedral group Dn of order 2n for odd number n. [ABSTRACT FROM AUTHOR]

Equal-square graph of finite group G is a simple finite undirected graph with vertex set G, in which two distinct vertices a, b are adjacent if and only if a² = b². In this research paper we have studied various structural properties such as connectivity, vertex degree, girth, clique number, independent number, chromatic number and matching number of Equal-square graph of finite groups. We have also calculated Laplacian polynomial and domination number of Equal-square graph of various finite groups. [ABSTRACT FROM AUTHOR]

For a prime p ≡ 3 (mod 4) and a positive integer t, let q = p 2 t . Let g be a primitive element of the finite field F q . The Peisert graph P ∗ (q) is defined as the graph with vertex set F q where ab is an edge if and only if a - b ∈ ⟨ g 4 ⟩ ∪ g ⟨ g 4 ⟩ . We provide a formula, in terms of finite field hypergeometric functions, for the number of complete subgraphs of order four contained in P ∗ (q) . We also give a new proof for the number of complete subgraphs of order three contained in P ∗ (q) by evaluating certain character sums. The computations for the number of complete subgraphs of order four are quite tedious, so we further give an asymptotic result for the number of complete subgraphs of any order m in Peisert graphs. [ABSTRACT FROM AUTHOR]

Let Δ be a one-dimensional simplicial complex on { 1 , 2 , ... , s } and S the polynomial ring K [ x 1 , ... , x s ] over a field K. The explicit formula for a 0 (S / I Δ n) is presented when girth (Δ) ≥ 4. If girth (Δ) = 3 we characterize the simplicial complexes Δ for which a 0 (S / I Δ n) = 3 n − 1 or 3 n − 2. [ABSTRACT FROM AUTHOR]

A subset I of the vertex set V (G) of a graph G is called a k - clique independent set of G if no k vertices in I form a k -clique of G. An independent set is a 2-clique independent set. Let π k (G) denote the number of k -cliques of G. For a function w : V (G) → { 0 , 1 , 2 , ... } , let G (w) be the graph obtained from G by replacing each vertex v by a w (v) -clique K v and making each vertex of K u adjacent to each vertex of K v for each edge { u , v } of G. For an integer m ≥ 1 , consider any w with ∑ v ∈ V (G) w (v) = m. For U ⊆ V (G) , we say that w is uniform on U if w (v) = 0 for each v ∈ V (G) ∖ U and, for each u ∈ U , w (u) = m / | U | or w (u) = m / | U | . Katona asked if π k (G (w)) is smallest when w is uniform on a largest k -clique independent set of G. He placed particular emphasis on the Sperner graph B n , given by V (B n) = { X : X ⊆ { 1 , ... , n } } and E (B n) = { { X , Y } : X ⊊ Y ∈ V (B n) }. He provided an affirmative answer for k = 2 (and any G). We determine graphs for which the answer is negative for every k ≥ 3. These include B n for n ≥ 2. Generalizing Sperner's Theorem and a recent result of Qian, Engel and Xu, we show that π k (B n (w)) is smallest when w is uniform on a largest independent set of B n. We also show that the same holds for complete multipartite graphs and chordal graphs. We show that this is not true of every graph, using a deep result of Bohman on triangle-free graphs. [ABSTRACT FROM AUTHOR]

Frei et al. (J. Comput. Syst. Sci. 123, 103–121, 2022) show that the stability, vertex stability, and unfrozenness problems with respect to certain graph parameters are complete for Θ 2 P , the class of problems solvable in polynomial time by parallel access to an NP oracle. They studied the common graph parameters α (the independence number), β (the vertex cover number), ω (the clique number), and χ (the chromatic number). We complement their approach by providing polynomial-time algorithms solving these problems for special graph classes, namely for graphs with bounded tree-width or bounded clique-width. In order to improve these general time bounds even further, we then focus on trees, forests, bipartite graphs, and co-graphs. [ABSTRACT FROM AUTHOR]

Major depressive disorder (MDD) is associated with complex disruptions in brain function, yet the underlying neural mechanisms remain incompletely understood. Traditional approaches to studying functional brain networks have primarily focused on pairwise interactions between brain regions, offering valuable insights into basic connectivity. However, such methods often fail to capture the complexity of higher-order interactions that are critical for understanding integrative processes in the brain. This study aims to address this gap by applying Q-analysis, a mathematical framework that extends beyond pairwise interactions, to fMRI-derived brain networks to investigate higher-order interactions and structural organization in individuals with MDD compared to healthy controls (HCs). Our analysis revealed significant alterations in the topology of brain networks in MDD patients, characterized by a lower maximum topology level and an increased prevalence of isolated edges and chains at the pairwise interaction level. The substantia nigra area demonstrated a higher topological dimension in MDD, suggesting its greater integration into disrupted network structures, potentially reflecting dopaminergic dysfunction associated with the disorder. Additionally, the consensus networks at higher topology levels indicated distinct network configurations between MDD patients and HCs, with the former exhibiting a single q-connected component primarily involving limbic, cerebellar, and occipital-temporal regions. We identified significant disruptions in the higher-order organizational structures of the brain, characterized by reduced topological diversity and complexity, fewer and less connected cliques, and altered involvement of key brain regions in MDD: the increased engagement of the limbic structures such as the substantia nigra, parahippocampal gyrus, and hippocampus, and decreased involvement of the cerebellum, the occipital and temporal lobes. Our study introduces a novel approach to understanding MDD pathophysiology through the lens of higher-order network structures, offering potential avenues for more targeted diagnostic and therapeutic strategies.

Graph neural networks have become a popular technique for collaborative filtering. However, most related work is based on user-item bipartite graphs, which can generate a large amount of noise due to the broad and elusive interests of users. To address this problem, we propose a novel generalized insertion framework (CGCN) that directly captures cliques in the item-item co-occurrence graph and considers them as the basic units of the user’s higher-order semantics. The method inserts the structural information in these item-item co-occurrence graphs as an insertion module into the original user-item bipartite graph propagation process, thus providing additional useful information to learn better feature representations. By utilizing the strong proximity relationships between different items in these cliques, the method is able to discover the user’s potential higher-order semantics. We experimentally evaluate two improved variants of the framework on three commonly used public datasets, and the results show significant performance improvements. The method is able to better discover users’ latent true intentions and achieve better recommender system performance by introducing clique information in the item-item co-occurrence graph.

In this paper, we study the class of graphs G m , n that have the same degree sequence as two disjoint cliques K m and K n , as well as the class G ¯ m , n of the complements of such graphs. The problems of finding a maximum clique and a maximum independent set are NP-hard on G m , n . Therefore, looking for upper and lower bounds for the clique and independence numbers of such graphs is a challenging task. In this article, we obtain such bounds, as well as other related results. In particular, we consider the class of regular graphs, which are degree-equivalent to arbitrarily many identical cliques, as well as such graphs of bounded degree. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a finite undirected graph with vertex set V (G) of order |V (G)| = n and edge set E(G) of size |E(G)| = m. Let ∆ = d1 ≥ d2 ≥ · · · ≥ dn = δ be the degree sequence of the graph G. A clique in a graph G is a complete subgraph of G. The clique number of a graph G, denoted by ω(G), is the order of a maximum clique of G. In 1907 Mantel proved that a triangle-free graph with n vertices can contain at most n 2 4 edges. In 1941 Turán generalized Mantel's result to graphs not containing cliques of size r by proving that graphs of order n that contain no induced Kr have at most (1 - 1/r-1)n²/2 edges. In this paper, we give new bounds for the maximum number of edges in a K r-free graph G of order n, minimum degree δ, and maximum degree ∆. We show that, for the families of graphs having the above properties, our bounds are slightly better than the more general bounds of Turán. [ABSTRACT FROM AUTHOR]

Link prediction is a crucial area of study within complex networks research. Mapping nodes to low-dimensional vectors through network embeddings is a vital technique for link prediction. Most of the existing methods employ "node–edge"-structured networks to model the data and learn node embeddings. In this paper, we initially introduce the Clique structure to enhance the existing model and investigate the impact of introducing two Clique structures (LECON: Learning Embedding based on Clique Of the Network) and nine motifs (LEMON: Learning Embedding based on Motif Of the Network), respectively, on experimental performance. Subsequently, we introduce a hypergraph to model the network and reconfigure the network by mapping hypermotifs to two structures: open hypermotif and closed hypermotif, respectively. Then, we introduce hypermotifs as supernodes to capture the structural similarity between nodes in the network (HMRLH: HyperMotif Representation Learning on Hypergraph). After that, taking into account the connectivity and structural similarity of the involved nodes, we propose the Depth and Breadth Motif Random Walk method to acquire node sequences. We then apply this method to the LEMON (LEMON-DB: LEMON-Depth and Breadth Motif Random Walk) and HMRLH (HMRLH-DB: HMRLH-Depth and Breadth Motif Random Walk) algorithms. The experimental results on four different datasets indicate that, compared with the LEMON method, the LECON method improves experimental performance while reducing time complexity. The HMRLH method, utilizing hypernetwork modeling, proves more effective in extracting node features. The LEMON-DB and HMRLH-DB methods, incorporating new random walk approaches, outperform the original methods in the field of link prediction. Compared with state-of-the-art baselines, the proposed approach in this paper effectively enhances link prediction accuracy, demonstrating a certain level of superiority. [ABSTRACT FROM AUTHOR]

Let G be a graph and S a subset of V (G). A graph G is called S - leaf-connected if G has a spanning tree T such that S is the set of leaves of T. For k ⩾ 2 , we say that a graph G is k - leaf-connected if | V (G) | > k and given any subset S of V (G) with | S | = k , G is S -leaf-connected. For 0 ≤ α < 1 , α -spectral radius of G is the spectral radius of A α (G) = α D (G) + (1 − α) A (G) , where D (G) and A (G) are the diagonal matrix of the vertex degrees and the adjacency matrix of G , respectively. In this paper, by utilizing the closure technique, we obtain a sufficient condition for a graph to be k -leaf-connected in terms of the number of cliques, which generalizes the result of Zhou et al. (2020). Furthermore, we give some sufficient conditions for a graph G to be k -leaf-connected in terms of α -spectral radius of G. [ABSTRACT FROM AUTHOR]

Ellis, Filmus, and Friedgut proved an old conjecture of Simonovits and Sós showing that any triangle-intersecting family of graphs on n vertices has size at most 2 ( n 2 ) − 3 , with equality for the family of graphs containing some fixed triangle. They conjectured that their results extend to cross-intersecting families, as well to K t -intersecting families. We prove these conjectures for t ∈ { 3 , 4 } , showing that if F 1 and F 2 are families of graphs on n labeled vertices such that for any G 1 ∈ F 1 and G 2 ∈ F 2 , G 1 ∩ G 2 contains a K t , then | F 1 | | F 2 | ≤ 4 ( n 2 ) − ( t 2 ) , with equality if and only if F 1 = F 2 consists of all graphs that contain some fixed K t. We also establish a stability result. More generally, " G 1 ∩ G 2 contains a K t " can be replaced by " G 1 and G 2 agree on a non- (t − 1) -colorable graph." [ABSTRACT FROM AUTHOR]

The maximum clique problem is a problem that takes many forms in optimization and related graph theory problems, and also has many applications. Because of its NP-completeness (nondeterministic polynomial time), the question arises of its solvability for larger instances. Instead of the traditional approaches based on the use of approximate or stochastic heuristic methods, we focus here on the use of integer programming models in the GAMS (General Algebraic Modelling System) environment, which is based on exact methods and sophisticated deterministic heuristics incorporated in it. We propose modifications of integer models, derive their time complexities and show their direct use in GAMS. GAMS makes it possible to find optimal solutions to the maximum clique problem for instances with hundreds of vertices and thousands of edges within minutes at most. For extremely large instances, good approximations of the optimum are given in a reasonable amount of time. A great advantage of this approach over all the mentioned algorithms is that even if GAMS does not find the best known solution within the chosen time limit, it displays its value at the end of the calculation as a reachable bound. [ABSTRACT FROM AUTHOR]

We prove that for k = 4 v n regular resolution requires length nO(k) to establish that an Erdős-Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent and also implies unconditional nO(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs. [ABSTRACT FROM AUTHOR]

AbstractThis article introduces complex Hadamard graphs and studies their properties. Using the complete subgraphs of these complex Hadamard graphs, complex Hadamard matrices of order n are generated, where n is a multiple of four. An algorithm to construct strongly regular graphs with n2 vertices using complex Hadamard matrices of order n is also discussed in this article. MAGMA codes to construct the adjacency matrices of these strongly regular graphs are also developed.

O número de Ramsey R(k,l) é o menor número inteiro n tal que não exista (k,l,n,e)-grafo, sendo que um (k,l,n,e)-grafo denota um grafo G com n vértices e e arestas e com C(G)

In this paper, we establish the clique connected common neighborhood polynomial of the graph resulting from the join of two connected graphs. [ABSTRACT FROM AUTHOR]

The widespread availability and importance of large-scale protein-protein interaction (PPI) data demand a flurry of research efforts to understand the organisation of a cell and its functionality by analysing these data at the network level. In the bioinformatics and data mining fields, network clustering acquired a lot of attraction to examine a PPI network's topological and functional aspects. The clustering of PPI networks has been proven to be an excellent method for discovering functional modules, disclosing functions of unknown proteins, and other tasks in numerous research over the last decade. This research proposes a unique graph mining approach to detect protein complexes using dense neighbourhoods (highly connected regions) in an interaction graph. Our technique first finds size-3 cliques associated with each edge (protein interaction), and then these core cliques are expanded to form high-density subgraphs. Loosely connected proteins are stripped out from these subgraphs to produce a potential protein complex. Finally, the redundancy is removed based on the Jaccard coefficient. Computational results are presented on the yeast and human protein interaction dataset to highlight our proposed technique's efficiency. Predicted protein complexes of the proposed approach have a significantly higher score of similarity to those used as gold standards in the CYC-2008 and CORUM benchmark databases than other existing approaches. [ABSTRACT FROM AUTHOR]

Let R be a ring with unity. In this paper, we introduce a new graph associated with R called the simple-intersection graph of R, denoted by GS(R). The vertices of GS(R) are the nonzero ideals of R, and two vertices are adjacent if and only if their intersection is a nonzero simple ideal. We study the interplay between the algebraic properties of R, and the graph properties of GS(R) such as connectedness, bipartiteness, girth, dominating sets, etc. Moreover, we determine the precise values of the girth and diameter of GS(R), as well as give a formula to compute the clique and domination numbers of GS(R).

We study reconfiguration problems for cliques in a graph, which determine whether there exists a sequence of cliques that transforms a given clique into another one in a step-by-step fashion. As one step of a transformation, we consider three different types of rules, which are defined and studied in reconfiguration problems for independent sets. We first prove that all the three rules are equivalent in cliques from the viewpoint of polynomial-time solvability. We then show that the problems are PSPACE-complete for perfect graphs, while we give polynomial-time algorithms for several classes of graphs, such as even-hole-free graphs and cographs. Furthermore, we show that the shortest variant, which computes the shortest length of a desired sequence, can be solved in polynomial time for chordal graphs, bipartite graphs, planar graphs, and bounded treewidth graphs. [ABSTRACT FROM AUTHOR]

Atomic cliques were introduced recently to analyze disease progression in temporal comorbidity graphs. Informally, an atomic clique is a clique that is unsplittable over time—the clique is either present or absent entirely and no parts of it appears in the temporal graph unless the entire clique is present. We consider the atomic counterpart of the classical maximum clique problem in this paper. Our main contribution is a polynomial-time algorithm that transforms the maximum atomic clique problem to the maximum clique problem on an auxiliary graph. We report results from our computational studies that demonstrate the effectiveness of this transformation in solving the maximum atomic clique problem in comparison to direct integer programming based approaches. The proposed approach is also applicable when solving variants like the minimum atomic clique partitioning problem or the maximum weighted atomic clique problem. [ABSTRACT FROM AUTHOR]

The need to determine the most appropriate data model increases, as the complexity of the designed computing systems and computer networks increases. The graph model is one of the main models for this kind of tasks. However, graphs are so complex for systems with many nodes, that heuristic methods, which are basic in graph theory, become too resource intensive. But it is possible to determine individual properties of graphs, as well as their parameters using the methods of the theory of multidimensional matrices, with significantly less computing power resources. This article discusses some properties of graphs that can be analyzed using the (λ,μ)-collapsed product of multidimensional matrices. The proofs of the correspondence of one of the numerical parameters of the vertices of the graph and the result of squaring the adjacency matrix of the graph are carried out. The parameters of the graph that do not affect its chromatic number are formulated, and an assumption is made about a possible relationship between the chromatic number and the number of odd cycles in the graph.

Let G be a 2-connected n-vertex graph and Ns(G) be the total number of s-cliques in G. Let k=4 and s=2 be integers. In this paper, we show that if G has an edge e which is not on any cycle of length at least k, then Ns(G)=r(k-1s)+(t+2s), where n-2=r(k-3)+t and 0=t=k-4. This result settles a conjecture of Ma and Yuan and provides a clique version of a theorem of Fan, Wang and Lv. As a direct corollary, if Ns(G)>r(k-1s)+(t+2s), every edge of G is covered by a cycle of length at least k. [ABSTRACT FROM AUTHOR]

The super line graph of index r, denoted by L r (G) , is defined for any graph G with at least r edges. Its vertices are the sets of r edges of G, and two such sets are adjacent if an edge of one is adjacent to an edge of the other. In this paper, we give an explicit characterization for all graphs G with L 2 (G) being a complete graph. We present lower bounds for the clique number and chromatic number of L 2 (G) for several classes of graphs. In addition, bounds for the domination number of L 2 (G) are established in terms of the domination number of the line graph L (G) of a graph. A number of related problems on L 2 (G) are proposed for a further study. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. A subset S of V(G) is called a local metric generator for G if for every two adjacent vertices u and v of G there exists a vertex w ∈ S such that d G (u , w) ≠ d G (v , w) where d G (x , y) is the distance between vertices x and y in G. The local metric dimension of G, denoted by dim ℓ (G) , is the minimum cardinality among all local metric generators of G. The clique number ω (G) of G is the cardinality of a maximum set of vertices that induce a complete graph in G. The authors in [Local metric dimension for graphs with small clique numbers. Discrete Math. 345 (2022), no. 4, Paper No. 112763] conjectured that if G is a connected graph of order n with ω (G) = k where 2 ≤ k ≤ n , then dim ℓ (G) ≤ k - 1 k n . In this paper, we prove this conjecture. Furthermore, we prove that equality in this bound is satisfied if and only if G is a complete graph K n . [ABSTRACT FROM AUTHOR]