Academic literature on the topic 'Non-isomorphic graph'

The adjacency spectrum [Formula: see text] of a graph [Formula: see text] is the multiset of eigenvalues of its adjacency matrix. Two graphs with the same spectrum are called cospectral. A graph [Formula: see text] is “determined by its spectrum” (DS for short) if every graph cospectral to it is in fact isomorphic to it. A group is DS if all of its Cayley graphs are DS. A group [Formula: see text] is Cay-DS if every two cospectral Cayley graphs of [Formula: see text] are isomorphic. In this paper, we study finite DS groups and finite Cay-DS groups. In particular we prove that a finite DS group is solvable, and every non-cyclic Sylow subgroup of a finite DS group is of order [Formula: see text], [Formula: see text], [Formula: see text] or [Formula: see text]. We also give several infinite families of non-Cay-DS solvable groups. In particular we prove that there exist two cospectral non-isomorphic [Formula: see text]-regular Cayley graphs on the dihedral group of order [Formula: see text] for any prime [Formula: see text].

If X is a connected graph, then an X-factor of a larger graph is a spanning subgraph in which all of its components are isomorphic to X. Given a set Γ of pairwise non-isomorphic graphs, a uniformly resolvable Γ-decomposition of a graph G is an edge decomposition of G into X-factors for some graph X∈Γ. In this article we completely solve the existence problem for decompositions of Kv-I into Cn-factors and K1,n-factors in the case when n is even.

Let G be a graph. The gamma graph of G denoted by γ ⋅ G is the graph with vertex set V(γ ⋅ G) as the set of all γ-sets of G and two vertices D and S of γ ⋅ G are adjacent if and only if |D ∩ S| = γ(G) – 1. A graph H is said to be a γ-graph if there exists a graph G such that γ ⋅ G is isomorphic to H. In this paper, we show that every induced subgraph of a γ-graph is also a γ-graph. Furthermore, if we prove that H is a γ-graph, then there exists a sequence {Gn} of non-isomorphic graphs such that H = γ ⋅ Gn for every n.

A graph is said to be DQS if there is no other non-isomorphic graph with the same signless Laplacian spectrum. For a DQS graph G, we show that G ? rK1 is DQS under certain conditions. Applying these results, some DQS graphs with isolated vertices are obtained.

The power graph P(G) of a group G is the graph with vertex set G and two distinct vertices are adjacent if one is a power of the other. Two finite groups are said to be conformal, if they contain the same number of elements of each order. Let Y be a family of all non-isomorphic odd order finite nilpotent groups of class two or p-groups of class less than p. In this paper, we prove that the power graph of each group in Y is isomorphic to the power graph of an abelian group and two groups in Y have isomorphic power graphs if they are conformal. We determine the number of maximal cyclic subgroups of a generalized extraspecial p-group (p odd) by determining the power graph of this group. We also determine the power graph of a p-group of order p4 (p odd).

A 3-connected graph is minimally 3-connected if removal of any edge destroys 3-connectivity. We present an algorithm for constructing minimally 3-connected graphs based on the results in (Dawes, JCTB 40, 159-168, 1986) using two operations: adding an edge between non-adjacent vertices and splitting a vertex. To test sets of vertices and edges for 3-compatibility, which depends on the cycles of the graph, we develop a method for obtaining the cycles of G′ from the cycles of G, where G′ is obtained from G by one of the two operations above. We eliminate isomorphic duplicates using certificates generated by McKay’s isomorphism checker nauty. The algorithm consecutively constructs the non-isomorphic minimally 3-connected graphs with n vertices and m edges from the non-isomorphic minimally 3-connected graphs with n−1 vertices and m−2 edges, n−1 vertices and m−3 edges, and n−2 vertices and m−3 edges.

The graph isomorphism problem (GI) plays a central role in the theory of computational complexity and has importance in physics and chemistry as well \cite{kobler93,fortin96}. No polynomial-time algorithm for solving GI is known. We investigate classical and quantum physics-based polynomial-time algorithms for solving the graph isomorphism problem in which the graph structure is reflected in the behavior of a dynamical system. We show that a classical dynamical algorithm proposed by Gudkov and Nussinov \cite{gudkov02} as well as its simplest quantum generalization fail to distinguish pairs of non-isomorphic strongly regular graphs. However, by combining the algorithm of Gudkov and Nussinov with a construction proposed by Rudolph \cite{rudolph02} in which one examines a graph describing the dynamics of two particles on the original graph, we find an algorithm that successfully distinguishes all pairs of non-isomorphic strongly regular graphs that we tested with up to 29 vertices.

Abstract Let G be a finite group. The subgroup intersection graph \text{Γ}(G) of G is a graph whose vertices are non-identity elements of G and two distinct vertices x and y are adjacent if and only if |\langle x\rangle \cap \langle y\rangle |\gt 1 , where \langle x\rangle is the cyclic subgroup of G generated by x. In this paper, we show that two finite abelian groups are isomorphic if and only if their subgroup intersection graphs are isomorphic.

In this paper, we initiate the study of spectrum of the commuting graphs of finite non-abelian groups. We first compute the spectrum of this graph for several classes of finite groups, in particular AC-groups. We show that the commuting graphs of finite non-abelian AC-groups are integral. We also show that the commuting graph of a finite non-abelian group G is integral if G is not isomorphic to the symmetric group of degree 4 and the commuting graph of G is planar. Further, it is shown that the commuting graph of G is integral if its commuting graph is toroidal.

The non-commuting graph associated to a non-abelian group [Formula: see text], [Formula: see text], is a graph with vertex set [Formula: see text] where distinct non-central elements [Formula: see text] and [Formula: see text] of [Formula: see text] are joined by an edge if and only if [Formula: see text]. The non-commuting graph of a non-abelian finite group has received some attention in existing literature. Recently, many authors have studied the non-commuting graph associated to a non-abelian group. In particular, the authors put forward the following conjectures: Conjecture 1. Let [Formula: see text] and [Formula: see text] be two non-abelian finite groups such that [Formula: see text]. Then [Formula: see text]. Conjecture 2 (AAM’s Conjecture). Let [Formula: see text] be a finite non-abelian simple group and [Formula: see text] be a group such that [Formula: see text]. Then [Formula: see text]. Some authors have proved the first conjecture for some classes of groups (specially for all finite simple groups and non-abelian nilpotent groups with irregular isomorphic non-commuting graphs) but in [Moghaddamfar, About noncommuting graphs, Sib. Math. J. 47(5) (2006) 911–914], Moghaddamfar has shown that it is not true in general with some counterexamples to this conjecture. On the other hand, Solomon and Woldar proved the second conjecture, in [R. Solomon and A. Woldar, Simple groups are characterized by their non-commuting graph, J. Group Theory 16 (2013) 793–824]. In this paper, we will define the same concept for a finite non-commutative Moufang loop [Formula: see text] and try to characterize some finite non-commutative Moufang loops with their non-commuting graph. Particularly, we obtain examples of finite non-associative Moufang loops and finite associative Moufang loops (groups) of the same order which have isomorphic non-commuting graphs. Also, we will obtain some results related to the non-commuting graph of a finite non-commutative Moufang loop. Finally, we give a conjecture stating that the above result is true for all finite simple Moufang loops.