Search

The intersection non-simple graph, denoted by INS(G), of a finite abelian group G is an undirected graph whose vertex set is the collection of all proper non-trivial subgroups of G, and any two distinct vertices are adjacent if and only if their intersection is not a simple subgroup of G. We obtain some properties of INS(G) related to connectedness, completeness, degree, and girth. The concepts of bipartiteness, triangle-free, cluster, claw-free and cograph are taken into consideration. We also investigate the clique number, independence number, domination number, and planarity of INS(G). [ABSTRACT FROM AUTHOR]

Given a 3-uniform hypergraph H , its 2-intersection graph G has as vertex set the hyperedges of H and e e ′ is an edge of G whenever e and e ′ have exactly two common vertices in H. Di Marco et al. prove in Di Marco et al. (2023) that deciding whether a graph G is the 2-intersection graph of a 3-uniform hypergraph is N P -complete. Following this result, we study the class of claw-free graphs. We show that the recognition problem remains N P -complete for that class, but becomes polynomial if we consider triangulated claw-free graphs. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with identity. The intersection graph of ideals of a ring R is an undirected simple graph denoted by Γ (R) whose vertices are in a one-to-one correspondence with non-zero proper ideals and two distinct vertices are joined by an edge if and only if the corresponding ideals of R have a non-zero intersection. Let M be a unitary R-module and let R ⋉ M be the idealization of M in R. In this paper, we investigate the interplay between the algebraic properties of R ⋉ M and the graph-theoretic properties of Γ (R ⋉ M) . Under some conditions on the ring R and the module M, we determine the exact form of ideals of R ⋉ M and characterize all rings R and modules M for which Γ (R ⋉ M) is a star graph. Also, we give a necessary and sufficient condition under which R ⋉ M is uniform and then we conclude that when Γ (R ⋉ M) is a complete graph. Among other results, some graph-theoretic properties of Γ (R ⋉ M) such as domination number, connectedness and grith are obtained. [ABSTRACT FROM AUTHOR]

The problem of intersection graphs was introduced by Szpilrajn-Marczewski in 1945. This study introduces a new variant of the intersection graph, called the k-restricted intersection graph. Let Sn be a nonempty n-element set, for some positive integer n, and let S(n,k) be the set of all the k-element subsets of Sn where 0 ≤ k ≤ n. A k-restricted intersection graph, denoted by GS(n,k), is a graph with vertex set S(n,k) such that two vertices A, B ∈ S(n,k) are adjacent whenever A ∩ B ̸= ∅ and A ̸= B. Here, we determined the order and size of GS(n,k) . Moreover, some parameters such as independence number, domination number, and isolate domination number of the k-restricted intersection graph were established. Finally, necessary and sufficient conditions for a GS(n,k) to be isomorphic to the cycle graph and complete graph were determined. [ABSTRACT FROM AUTHOR]

IntroductionAn elastic-degenerate (ED) string is a sequence of sets of strings. It can also be seen as a directed acyclic graph whose edges are labeled by strings. The notion of ED strings was introduced as a simple alternative to variation and sequence graphs for representing a pangenome, that is, a collection of genomic sequences to be analyzed jointly or to be used as a reference.MethodsIn this study, we define notions of matching statistics of two ED strings as similarity measures between pangenomes and, consequently infer a corresponding distance measure. We then show that both measures can be computed efficiently, in both theory and practice, by employing the intersection graph of two ED strings.ResultsWe also implemented our methods as a software tool for pangenome comparison and evaluated their efficiency and effectiveness using both synthetic and real datasets.DiscussionAs for efficiency, we compare the runtime of the intersection graph method against the classic product automaton construction showing that the intersection graph is faster by up to one order of magnitude. For showing effectiveness, we used real SARS-CoV-2 datasets and our matching statistics similarity measure to reproduce a well-established clade classification of SARS-CoV-2, thus demonstrating that the classification obtained by our method is in accordance with the existing one.

Let $G$ be a finite non-trivial group. The intersection graph $\Gamma(G)$, is a graph whose vertices are all proper non-trivial subgroups of $G$, and there is an edge between two distinct vertices $H $ and $K$ if and only if $H\cap K\neq 1$. In this paper, we determine the clique number of the intersection graph of the cyclic groups of orders having at most three primes in their decomposition.1. IntroductionLet $G$ be a finite group. There are several ways to associate a graph to $G$ (see [7] and the references therein). The one we will consider in this paper, is denoted by $\Gamma(G)$ and is called the intersection graph of $G$. The intersection graph $\Gamma(G)$ of a nontrivial group $G$ is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of $G$, and there is an edge between two distinct vertices $H $ and $K$ if and only if $H\cap K\neq 1$ where 1 denotes the trivial subgroup of $G$. The graph $\Gamma(G)$ has been extensively studied ( see, for example, [1, 8, 11, 12]). Currently, the present authors in [4], have determined all groups $G$ such that the clique number of $\Gamma(G)$ is less than 5, and also they have given a criterion for solvability of finite groups $G$, by the clique number of $\Gamma(G)$. More precisely, it has been proved that if $G$ is a finite group such that the clique number of $\Gamma(G)$ is less than 13, then $G$ is solvable. Note that 13 is the clique number of $\Gamma(A_5)$, where $A_5$ is the alternating group on 5 letters. Other researches in this topic are intersection graphs of a semigroup, a module, and ideals of a ring, were investigated in [5], [2] and [6, 10], respectively. 2. Main ResultsWe start this section with the following definition:Definition 2.1. The subset $X$ of vertices of a finite graph $\Gamma$ is called a {\it clique}, if the induced subgraph by $X$ is a complete graph. The maximum size of a clique, among all cliques of $\Gamma$, is called the clique number of $\Gamma$ and we denote it by $\omega(\Gamma)$. If $\Gamma$ is empty (without vertex), then we define $\omega(\Gamma)=0$ and $\omega(\Gamma)=1$ if $\Gamma$ is null (with a non-empty vertex set with no edges). A clique $X$ in $\Gamma$ is called {\it maximal} if there is no clique $Y$ in $\Gamma$ such that $X\subsetneq Y$. Note that the maximum size, among all maximal cliques in $\Gamma(G)$, is $\omega(\Gamma(G))$. To prove the main theorems, we need the following result that its proof can be found in the most valid book of group theory. Proposition 2.2. If $G=\langle g\rangle$ is a cyclic group of ordsr $n$, then for any divisor $s$ of $n$, there is a unique subgroup $H=\langle g^{\frac{n}{s}}\rangle$ of $G$ of order $s$. The following result is a consequence of the above proposition. Corollary 2.3. Let $G$ be a finite cyclic group. Then, the intersection of two proper subgroups of $G$ is non-trivial if and only if their orders are not relatively prime. For a natural number $n$, we denote by $C_n$ the cyclic group of order $n$, $\pi(n)$ the set of prime divisors of $n$ and $d(n)$ the number of all divisors of $n$. Note that if $p$ is a prime number and $n$ is a multiple of $p$, then the number of divisors of $n$ with multiple $p$ is $d(\frac{n}{p})$. If $V(\Gamma(G))$ is the set of vertices of $\Gamma(G)$, then by Proposition 2.2, we have $|V(\Gamma(C_n))|=d(n)-2$. In this paper, we obtain $\omega(\Gamma(C_n))$, where $|\pi(n)|=3$. 3. Summary of Proofs/ConclusionsNow, we state and prove our main results. First, we find the clique number of a cyclic group of a prime power order. Proposition 3.1. If $p$ is a prime and $m$ is a positive integer, then $\omega(\Gamma(C_{p^m}))=m-1$.Proof. Since $|V(\Gamma(C_n))|=d(n)-2$ and $d(p^m)=m+1$, we get the conclusion. In the sequel, assume that $p_1, p_2$ and $p_3$ are distinct primes. Also assume that $n_1, n_2$ and $n_3$ are positive integers such that $n_1\geq n_2\geq n_3$. In the following results, we obtain the clique number of the intersection graph of group $C_{p_1^{n_1}p_2^{n_2}}$. We recall that $d(p_1^{n_1}p_2^{n_2})=(n_1+1)(n_2+1)$. Proposition 3.2. We have$\omega(\Gamma(C_{p_1^{n_1}p_2^{n_2}}))=d(p_1^{n_1}p_2^{n_2})-2-d(p_2^{n_2})=n_1n_2+n_1-1$. Proof. Suppose that $G=C_{p_1^{n_1}p_2^{n_2}}$. Then, we define the subsets of $V(\Gamma(G))$ as follows: ♦ For $1\leq i\leq 2$, $V_{p_i}(\Gamma(G))$ is the set of all proper subgroups $H$ of $G$ such that $\pi(|H|)=\{p_i\}$. ♦ $V_{p_1p_2}(\Gamma(G))$ is the set of all proper subgroups $H$ of $G$ such that $\pi(|H|)=\{p_1, p_2\}$. It is clear that $\{V_{p_1}(\Gamma(G)), V_{p_2}(\Gamma(G)), V_{p_1p_2}(\Gamma(G)) \}$ forms a partition for $V(\Gamma(G))$. By Proposition 2.2, we have $|V_{p_i} (\Gamma(G))|=d(p_i^{n_i})-1=n_i$ and $|V_{p_1p_2}(\Gamma(G))|=d(\frac{n}{p_1p_2})-1=n_1n_2-1$. By Corollary 2.3, in $\Gamma(G)$, each element of the clique $V_{p_1}(\Gamma(G))$ does not join to any element of the clique $V_{p_2}(G)$ and moreover all elements of $V_{p_i}(\Gamma(G))$ for $i=1, 2$ join to all elements of the clique $V_{p_1p_2}(G)$. Therefore $V_{p_1}(\Gamma(G))\cup V_{p_1p_2}(\Gamma(G))$ and $V_{p_2}(\Gamma(G))\cup V_{p_1p_2}(\Gamma(G))$ are the only maximal cliques of $\Gamma(G)$ and since $n_1\geq n_2$, we have the result.Now we state the last main result. Theorem 3.3. Let $G= C_n$ where $n=p_1^{n_1}p_2^{n_2}p_3^{n_3}$. Then\\(1) If $n_1\geq n_2n_3$, then $\omega(\Gamma(G))=d(\frac{n}{p_1})-1=n_1+n_1n_2+n_1n_3+n_1n_2n_3-1$.\\(2) If $n_1\leq n_2n_3$, then $\omega(\Gamma(G))=d(\frac{p_1^{n_1}p_2^{n_2}}{p_1p_2})+d(\frac{p_1^{n_1}p_3^{n_3}}{p_1p_3})+d(\frac{p_2^{n_2}p_3^{n_3}}{p_2p_3})+d(\frac{n}{p_1p_2p_3})-1$\\$$\hspace{5cm}=n_1n_2+n_1n_3+n_2n_3+n_1n_2n_3-1.~~~~~~~~~~~~~~~~~~~~~~~\hspace{4cm}$$Proof. Similar to the proof of Proposition 3.2, we define the subsets of $V(\Gamma(G))$ as follows:\\♦ For $1\leq i\leq 3$, $V_{p_i}(\Gamma(G))$ is the set of all subgroups $H$ of $G$ such that $\pi(|H|)=\{p_i\}$. Therefore, $|V_{p_i}(\Gamma(G))|=d(p_i^{n_i})-1=n_i$.♦ $V_{p_ip_j}(\Gamma(G))$ is the set of all subgroups $H$ of $G$ such that $\pi(|H|)=\{p_i, p_j\}$ for $1\leq i

A correction is presented to the article "Correction To on The Complement Of The Zero-divisor Graph Of A Partially Ordered Set" published in a previous issue of the periodical.

The disjointness graph of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph G of any system of segments in the plane is χ-bounded , that is, its chromatic number χ (G) is upper bounded by a function of its clique number ω (G). Here we show that this statement does not remain true for systems of polygonal chains of length 2. We also construct systems of polygonal chains of length 3 such that their disjointness graphs have arbitrarily large girth and chromatic number. In the opposite direction, we show that the class of disjointness graphs of (possibly self-intersecting) 2 -way infinite polygonal chains of length 3 is χ -bounded: for every such graph G , we have χ (G) ≤ (ω (G)) 3 + ω (G). [ABSTRACT FROM AUTHOR]

For a nontrivial finite group G, the intersection graph Γ (G) of G is the simple undirected graph whose vertices are the nontrivial proper subgroups of G and two vertices are joined by an edge if and only if they have a nontrivial intersection. In a finite simple graph Γ , the clique number of Γ is denoted by ω (Γ) . In this paper we show that if G is a finite group with ω (Γ (G)) < 13 , then G is solvable. As an application, we characterize all non-solvable groups G with ω (Γ (G)) = 13 . Moreover, we determine all finite groups G with ω (Γ (G)) ∈ { 2 , 3 , 4 } . [ABSTRACT FROM AUTHOR]

Geography, for example because of the presence of rivers, ravines, or peaks, can subdivide a city. These subdivisions raise the question of identifying the area occupied by the city, of deciding whether or not they are aggregates of distinct built-up areas, and whether or not geographical separations are merely asperities in a certain continuum of built-up areas. The city as a union of administrative units allows for jurisdictional practices, but for public policy in health for example, identification by built-up areas is more operational. The study of urban populations thus requires that cities be circumscribed on objective criteria. Circumscribing a city requires knowledge of commuting flows, but in the absence of this piece of information, circumscribing it relies on the fact that it is made up of close built-up areas. This is reflected in the intersection of the convex envelopes of the spatial extent of these built-up areas. The algorithm treats coordinates of the vertices of polygons encompassing built-up areas provided by the Census Bureau for the United States or the National Institute of Statistics and Geography for Mexico. It allows for computing whether convex hulls of polygons intersect or not. If they do, then the built-up areas circumscribed by these polygons are part of the same city. The result is that cities now reflect the geographic extent of urban areas rather than their administrative areas. With this delineation method applied to Mexico's 2020 census data, the population sizes of urban areas with at least 2,126 inhabitants follow a power law, with exponent 0.954 (standard deviation = 0.016), whereas this is no longer the case when considering only the administrative extents of cities with more than 15,000 inhabitants. [ABSTRACT FROM AUTHOR]

Various characteristics of the algebraic structures can be expressed by associating it to the graphs of different groups. In an intersection graph, each vertex conforms to a set wherein two vertices are connected by an edge if and only if their corresponding sets have a nonempty intersection. For a finite group G, a graph of its subgr can be represented by the vertices that correspond to the subgroups of G. Based on this factor, we defined the cyclic intersection graph of the subgroups of a group G. The cyclic intersection graph of the subgroups of a group G enclosed all the nontrivial subgroups as its vertices together with two adjacent vertices H and K if and only if H intersection K corresponded to a non-trivial cyclic subgroup. Furthermore, the general presentation of the graph on the dihedral groups was obtained. The cyclic intersection graph of the subgroups on dihedral groups is classified as connected or planar. Additionally, some of the invariants of the the cyclic intersection graph of the subgroups on the dihedral groups are given. [ABSTRACT FROM AUTHOR]

A simple but powerful network model with n$$ n $$ nodes and m$$ m $$ partly overlapping layers is generated as an overlay of independent random graphs G1,...,Gm$$ {G}_1,\dots, {G}_m $$ with variable sizes and densities. The model is parameterized by a joint distribution Pn$$ {P}_n $$ of layer sizes and densities. When m$$ m $$ grows linearly and Pn→P$$ {P}_n\to P $$ as n→∞$$ n\to \infty $$, the model generates sparse random graphs with a rich statistical structure, admitting a nonvanishing clustering coefficient together with a limiting degree distribution and clustering spectrum with tunable power‐law exponents. Remarkably, the model admits parameter regimes in which bond percolation exhibits two phase transitions: the first related to the emergence of a giant connected component, and the second to the appearance of gigantic single‐layer components. [ABSTRACT FROM AUTHOR]

We introduce k-maximal sub-polygon graphs (k-MSP graphs), the intersection graphs of maximal polygons contained in a polygon with sides parallel to a regular 2k-gon. We prove that all complete graphs are k-MSP graphs for all k > 1 ; trees are 2-MSP graphs; trees are k-MSP graphs for k > 2 if and only if they are caterpillars; and n-cycles are not k-MSP graphs for n > 3 and k > 1 . We derive bounds for which j-cycles appear as induced subgraphs of k-MSP graphs. As our main result, we construct examples of graphs which are k-MSP graphs and not j-MSP graphs for all k > 1 , j > 1 , k ≠ j . [ABSTRACT FROM AUTHOR]

Let G be a group. In this paper, we introduce and study the intersection subgroup graph of G as the (simple) graph Γ S (G) with vertices the nontrivial subgroups H of G such that H ∩ K = { e } for some nontrivial subgroup K of G, and distinct vertices H and K are adjacent if and only if H ∩ K = { e } . We investigate when Γ S (G) is a nonempty, finite, complete, complete bipartite, or planar graph. [ABSTRACT FROM AUTHOR]

The classical Hadamard-Fischer-Koteljanskii inequality is an inequality between principal minors of positive definite matrices. In this work, we present an extension of the Hadamard-Fischer-Koteljanskii inequality, that is inspired by the inclusion-exclusion formula for sets. We formulate necessary and sufficient conditions for the inequality to hold. We describe general structures of the collection of index sets involved. In analyzing these structures, a graph-theoretical property that applies to bipartite graphs is found. We establish that if the vertices of a bipartite graph satisfy simple conditions, then the bipartite graph contains a vertex subgraph which is a cycle or a complete subgraph missing a matching. This result is reminiscent of the Hall's marriage theorem for bipartite graphs. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to introduce the notion of intersection graphs based on non-trivial hyperideals in general hyperrings. In order to realise the article's goals, we design general hyperrings on any given ring and compute the set of all hyperideals of related general hyperring. Moreover to establish of connection between of hyperideals as vertices of it's associated graph, we introduce the concept of absorbing elements. The main method in this research is based on nonempty intersection of hyperideals, so we discuss on divisor of order of general hyperrings. As a result of the research, is constructing of some necessary and sufficient conditions in intersection graphs to be a connected(complete, Hamiltonian, or Eulerian) graph. Also, is presented notations of annihilator and kernel of homomorphisms via absorbing elements and fundamental relations. The paper includes implications for the development of intersection graph, for modelling the complex hypernetworks by absorbing elements, prime divisors and their relations in hyperideals. The new conception of intersection graphs based on hyperideals of general hyperrings was broached for the in this paper first time. [ABSTRACT FROM AUTHOR]

An H-graph is one representable as the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró et al. (Discrete Mathematics 100:267–279, 1992). An H-graph is proper if the representing subgraphs of H can be chosen incomparable by the inclusion. In this paper, we focus on the isomorphism problem for S d -graphs and T-graphs, where S d is the star with d rays and T is an arbitrary fixed tree. Answering an open problem of Chaplick et al. (2016, personal communication), we provide an FPT-time algorithm for testing isomorphism and computing the automorphism group of S d -graphs when parameterized by d, which involves the classical group-computing machinery by Furst et al. (in Proceedings of 11th southeastern conference on combinatorics, graph theory, and computing, congressum numerantium 3, 1980). We also show that the isomorphism problem of S d -graphs is at least as hard as the isomorphism problem of posets of bounded width, for which no efficient combinatorial-only algorithm is known to date. Then we extend our approach to an XP-time algorithm for isomorphism of T-graphs when parameterized by the size of T. Lastly, we contribute an FPT-time combinatorial algorithm for isomorphism testing in the special case of proper S d - and T-graphs. [ABSTRACT FROM AUTHOR]

This paper is inspired by the well known characterization of chordal graphs as the intersection graphs of subtrees of a tree. We consider families of induced trees of any graph and we prove that their recognition is NP-Complete. A consequence of this fact is that the concept of clique tree of chordal graphs cannot be widely generalized. Finally, we consider the fact that every graph is the intersection graph of induced trees of a bipartite graph and we characterize some classes that arise when we impose restrictions on the host bipartite graph. [ABSTRACT FROM AUTHOR]

In this article, we introduce and study the intersection graph of graded submodules of a graded module. Let MM be a left GG-graded RR-module. We define the intersection graph of GG-graded RR-submodules of MM, denoted by Γ(G,R,M)\Gamma \left(G,R,M), to be a simple undirected graph whose set of vertices consists of all nontrivial GG-graded RR-submodules of MM, where two vertices are adjacent if their intersection is nonzero. We study properties of these graphs, such as connectivity, diameter, and girth. We also investigate the intersection graph of graded submodules for certain types of gradings such as faithful and strong gradings.

We consider the problem of designing succinct navigational oracles, i.e., succinct data structures supporting basic navigational queries such as degree, adjacency and neighborhood efficiently for intersection graphs on a circle, which include graph classes such as circle graphs , k-polygon-circle graphs , circle-trapezoid graphs , trapezoid graphs. The degree query reports the number of incident edges to a given vertex, the adjacency query asks if there is an edge between two given vertices, and the neighborhood query enumerates all the neighbors of a given vertex. We first prove a general lower bound for these intersection graph classes, and then present a uniform approach that lets us obtain matching lower and upper bounds for representing each of these graph classes. More specifically, our lower bound proofs use a unified technique to produce tight bounds for all these classes, and this is followed by our data structures which are also obtained from a unified representation method to achieve succinctness for each class. In addition, we prove a lower bound of space for representing trapezoid graphs, and give a succinct navigational oracle for this class of graphs. [ABSTRACT FROM AUTHOR]

Introduction: An elastic-degenerate (ED) string is a sequence of sets of strings. It can also be seen as a directed acyclic graph whose edges are labeled by strings. The notion of ED strings was introduced as a simple alternative to variation and sequence graphs for representing a pangenome, that is, a collection of genomic sequences to be analyzed jointly or to be used as a reference., Methods: In this study, we define notions of matching statistics of two ED strings as similarity measures between pangenomes and, consequently infer a corresponding distance measure. We then show that both measures can be computed efficiently, in both theory and practice, by employing the intersection graph of two ED strings., Results: We also implemented our methods as a software tool for pangenome comparison and evaluated their efficiency and effectiveness using both synthetic and real datasets., Discussion: As for efficiency, we compare the runtime of the intersection graph method against the classic product automaton construction showing that the intersection graph is faster by up to one order of magnitude. For showing effectiveness, we used real SARS-CoV-2 datasets and our matching statistics similarity measure to reproduce a well-established clade classification of SARS-CoV-2, thus demonstrating that the classification obtained by our method is in accordance with the existing one., Competing Interests: The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest., (Copyright © 2024 Gabory, Mwaniki, Pisanti, Pissis, Radoszewski, Sweering and Zuba.)

Let L(R) denote the set of all non-trivial left ideals of a ring R. The intersection graph of ideals of a ring R is an undirected simple graph denoted by G(R) whose vertices are in a one-to-one correspondence with L(R) and two distinct vertices are joined by an edge if and only if the corresponding left ideals of R have a non-zero intersection. The ideal structure of a ring reflects many ring theoretical properties. There is so much research that has been conducted during the last decade to explore the properties of G(R). This is a survey of the developments in the study on the intersection graphs of ideals of rings since its introduction in 2009. [ABSTRACT FROM AUTHOR]

In this article, we introduce and study the intersection graph of graded ideals of a graded ring. The intersection graph of G−graded ideals of a graded ring R, denoted by GrG(R), is undirected simple graph defined on the set of nontrivial graded left ideals of R, such that two left ideals are adjacent if their intersection is not trivial. We study properties for these graphs such as connectivity, regularity, completeness, domination numbers, and girth. We also present several results on the intersection graphs related to faithful grading, strong grading, and graded idealization.

The orthogonal disjunctive normal forms (DNFs) of Boolean functions have wide applications in the logical design of discrete devices. The problem of DNF orthogonalization is to get for a given function such a DNF that any two its terms would be orthogonal, i. e. the conjunction of them would be equal identically to zero. An approach to solve the problem using the means of graph theory is suggested. The approach is proposed by representation of the function as perfect DNF. Obtaining all the intervals of the Boolean space where the given function has value 1 is supposed, and the intersection graph of those intervals is considered. Two methods to obtain a minimum orthogonal DNF are considered. One of them reduces the problem toward finding out the smallest dominating set in the graph by covering its vertices with their closed neighborhoods, the other - to obtain the maximum independent set by lexicographic enumeration. It is shown how the suggested approach can be extended on incompletely specified Boolean functions.

In the paper such subclass of string graphs as intersection graphs of closed polygonal chains (class of CPC-graphs) was considered, necessary conditions for belonging to that class, forbidden subgraphs and operations with graphs which preserve belonging to the CPC class were found. Considered question about the existence of k-regular CPC-graphs, particularly, pairs (k, n), such that there exists k-regular CPC-graph on n vertexes were found, proved that there are infinitely many k-regular CPC-graphs for any k ∈ N, estimations for the number of k, such that k-regular graph on n vertexes exists, were given. Algorithmic questions in the class of CPC-graphs were investigated. It was proved that independent and dominating set problems, coloring problem and the problem about maximal cycle are NP-hard in the class of CPC-graphs, and problem of recognition of the CPC-graphs belongs to the PSPACE class.

Let (P, ≤) be a poset with the least element 0. The intersection graph of ideals of P, denoted by G(P), is a graph whose vertices are all nontrivial ideals of P and two distinct vertices I and J are adjacent if and only if I ∩ J ≠ {0}. In this paper, we study the planarity and outerplanarity of the intersection graph G(P). Also, we determine all posets with split intersection graphs.

For any nonempty set Ω and k-subset Λ, the k-intersection graph, denoted by Γm(Ω,Λ), is an undirected simple graph whose vertices are all m-subsets of Ω and two distinct vertices A and B are adjacent if and only if A∩B ⊈ Λ. In this paper, we determine diameter, girth, some numerical invariants and planarity, Hamiltonian and perfect matching of these graphs. finally we investigate their adjacency matrices.

A polynomial associated with G is defined as t (G , w) = ∑ T ∈ T (G) ∏ e ∈ E (T) w e (G) ( T (G) is the set of spanning trees of G), which is a weighted enumeration of spanning trees of graphs. It is known that any graph G is an intersection graph of a linear hypergraph, which corresponds to a clique partition of G. In this paper, we introduce the Schur complement formula and local transformation formula of t(G, w). By using these formulas, we obtain some expressions of t(G, w) for weighted intersection graphs and express the number of spanning trees of graph G in terms of clique partitions of G. As applications, expressions for enumerating spanning trees in bipartite graphs, line graphs, generalized line graphs, middle graphs, total graphs, generalized join graphs and vertex-weighted graphs are derived from our work. [ABSTRACT FROM AUTHOR]

Let G be a non-abelian finite simple group. In addition, let Δ G be the intersection graph of G, whose vertices are the proper non-trivial subgroups of G, with distinct subgroups joined by an edge if and only if they intersect non-trivially. We prove that the diameter of Δ G has a tight upper bound of 5, thereby resolving a question posed by Shen (Czechoslov Math J 60(4):945–950, 2010). Furthermore, a diameter of 5 is achieved only by the baby monster group and certain unitary groups of odd prime dimension. [ABSTRACT FROM AUTHOR]

Let R be an unital ring which is not necessarily commutative. The intersection graph of ideals of R is a graph with the vertex set which contains proper ideals of R and distinct two vertices I and J are adjacent if and only if I Ç J ¹ 0 is denoted by G. In this paper, we will give some properties of regular graph, triangle-free graph and clique number of G(M) for a module M. We also characterize girth of an Artinian module with connected module. We characterize the chromatic number of G(Zn). We also give an algorithm for the chromatic number of G(Zn). [ABSTRACT FROM AUTHOR]

In this paper, we determine the computational complexity of recognizing two graph classes, grounded L -graphs and stabbable grid intersection graphs. An L -shape is made by joining the bottom end-point of a vertical (|) segment to the left end-point of a horizontal (−) segment. The top end-point of the vertical segment is known as the anchor of the L -shape. Grounded L -graphs are the intersection graphs of L -shapes such that all the L -shapes' anchors lie on the same horizontal line. We show that recognizing grounded L -graphs is NP -complete. This answers an open question asked by Jelínek & Töpfer (Electron. J. Comb., 2019). Grid intersection graphs are the intersection graphs of axis-parallel line segments in which two vertical (similarly, two horizontal) segments cannot intersect. We say that a (not necessarily axis-parallel) straight line ℓ stabs a segment s , if s intersects ℓ. A graph G is a stabbable grid intersection graph (▪) if there is a grid intersection representation of G in which the same line stabs all its segments. We show that recognizing ▪ graphs is NP -complete, even on a restricted class of graphs. This answers an open question asked by Chaplick et al. (O rder, 2018). [ABSTRACT FROM AUTHOR]

Let be a commutative ring and be a unital -module. The intersection graph of submodules of , denoted by , is the graph whose vertex set is the collection of all submodules of and in which two distinct vertices and are adjacent if and only if . In this paper the notion of essentiality of modules plays a vital role in the study of intersection graph of submodules of . This notion gives a new dimension in characterizing the center of intersection graphs of submodules of . We define mna (maximal non-adjacent) vertex in and observe some of its characteristics. The notion of complemented intersection graph exhibits some significant algebraic and graphical properties. Moreover, defining the concept of isolated center in we establish certain results related to mna vertex.

< p>The intersection graph $\\mathbb{Int}(A)$ of an $S$-act $A$ over a semigroup $S$ is an undirected simple graph whose vertices are non-trivial subacts of $A$, and two distinct vertices are adjacent if and only if they have a non-empty intersection. In this paper, we study some graph-theoretic properties of $\\mathbb{Int}(A)$ in connection to some algebraic properties of $A$. It is proved that the finiteness of each of the clique number, the chromatic number, and the degree of some or all vertices in $\\mathbb{Int}(A)$ is equivalent to the finiteness of the number of subacts of $A$. Finally, we determine the clique number of the graphs of certain classes of $S$-acts.

For a finite group G, Γ(G), the intersection graph of G, is a simple graph whose vertices are all nontrivial proper subgroups of G and two distinct vertices H and K are adjacent when H ∩ K ≠ 1. In this paper, we classify all finite nonsimple groups whose intersection graphs have a leaf and also we discuss the characterizability of them using their intersection graphs. [ABSTRACT FROM AUTHOR]

Let F be a field and GL n (F) the general linear group of degree n > 1 over F. The intersection graph Γ ( GL n (F)) of GL n (F) is a simple undirected graph whose vertex set includes all nontrivial proper subgroups of GL n (F). Two vertices A and B of Γ ( GL n (F)) are adjacent if A ≠ B and A ∩ B ≠ { I n }. In this paper, we show that if F is a finite field containing at least three elements, then the diameter δ (Γ ( GL n (F))) is 2 or 3. We also classify GL n (F) according to δ (Γ ( GL n (F))). In case F is infinite, we prove that Γ ( GL n (F)) is one-ended of diameter 2 and its unique end is thick. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with identity and I ∗ (R) , the set of all nontrivial proper ideals of R. The intersection graph of ideals of R , denoted by ℐ (R) , is a simple undirected graph with vertex set as the set I ∗ (R) , and, for any two distinct vertices I and J are adjacent if and only if I ∩ J ≠ (0). In this paper, we study some connections between commutative ring theory and graph theory by investigating topological properties of intersection graph of ideals. In particular, it is shown that for any nonlocal Artinian ring R , ℐ (R) is a projective graph if and only if R ≅ R 1 × F 1 , where R 1 is a local principal ideal ring with maximal ideal 𝔪 1 of nilpotency three and F 1 is a field. Furthermore, it is shown that for an Artinian ring R , γ ¯ (ℐ (R)) = 2 if and only if R ≅ R 1 × R 2 , where each R i (1 ≤ i ≤ 2) is a local principal ideal ring with maximal ideal 𝔪 i ≠ (0) such that 𝔪 i 2 = (0). [ABSTRACT FROM AUTHOR]

Consider finitely many points in a geodesic space. If the distance of two points is less than a fixed threshold, then we regard these two points as "near". Connecting near points with edges, we obtain a simple graph on the points, which is called a unit ball graph. If the space is the real line, then it is known as a unit interval graph. Unit ball graphs on a geodesic space describe geometric characteristics of the space in terms of graphs. In this article, we show that every unit ball graph on a geodesic space is (strongly) chordal if and only if the space is an R -tree and that every unit ball graph on a geodesic space is (claw, net)-free if and only if the space is a connected manifold of dimension at most 1. As a corollary, we prove that the collection of unit ball graphs essentially characterizes the real line and the unit circle. [ABSTRACT FROM AUTHOR]

The paper introduces a new notion that is a graph of crossroad transport flows. It has been shown that the given graph serves as a unification of conflict graphs. The paper provides numerical characteristics of graphs on conflict interaction of transport flows in the process of their merging and intersection at crossroads of various configuration. The following construction of the graph has been carried out: merging graphs where their nodes correspond to conflicting flows and their edges indicate what flows enter into a merging conflict between themselves; intersection graphs where graph nodes correspond to conflicting flows and their edges indicate what flows enter into an intersection conflict between themselves. Taking into account the conflict interaction between traffic and pedestrian flows, traffic conditions and traffic trajectories before possible physical interaction the traffic flow graph takes such form which contains complete information about existing conflicts for the required intersection. As a result of the construction in accordance with theoretical aspects of a graph theory and actual interaction of transport and pedestrian flows at intersections, some regularities have been revealed that allow to estimate a danger of any particular intersection within the urban street-road network. The proposals can be identified as hazard markers of an object and that is especially topical with due account of available actual data on driving regimes, traffic light regulation, flow intensity and driving speed (especially single vehicles exceeding permissible driving speed for urban traffic or taking into account local restrictions on certain sections of street-road network) which form a vehicle or pedestrian graph. The proposed approaches can be used to assess quality of road traffic in conflict areas of the street-road network in cities and settlements and public roads as well.