The lattice of closure operators on a subgroup lattice

We say a lattice L is a subgroup lattice if there exists a group G such that Sub(G)?L, where Sub(G) is the lattice of subgroups of G, ordered by inclusion. We prove that the lattice of closure operators which act on the subgroup lattice of a finite group G is itself a subgroup lattice if and only if G is cyclic of prime power order.     

On the lattice formed by all normal subloops of a finite loop

All normal subloops of a loopG form a modular latticeL _n (G). It is shown that a finite loopG has a complemented normal subloop lattice if and only ifG is a direct product of simple subloops. In particular,L _n (G) is a Boolean algebra if and only if no two isomorphic factors occurring in a decomposition ofG are abelian groups. The normal subloop lattice of a finite loop is a projective geometry if and only ifG is an elementary abelianp-group for some primep.     

Noncyclic Graph of a Group

We associate a graph Γ _G to a nonlocally cyclic group G (called the noncyclic graph of G) as follows: take G\ Cyc(G) as vertex set, where Cyc(G) = {x ? G| 〈x, y〉 is cyclic for all y ? G}, and join two vertices if they do not generate a cyclic subgroup. We study the properties of this graph and we establish some graph theoretical properties (such as regularity) of this graph in terms of the group ones. We prove that the clique number of Γ _G is finite if and only if Γ _G has no infinite clique. We prove that if G is a finite nilpotent group and H is a group with Γ _G  ? Γ _H and |Cyc(G)| = |Cyc(H)| = 1, then H is a finite nilpotent group. We give some examples of groups G whose noncyclic graphs are “unique”, i.e., if Γ _G  ? Γ _H for some group H, then G ? H. In view of these examples, we conjecture that every finite nonabelian simple group has a unique noncyclic graph. Also we give some examples of finite noncyclic groups G with the property that if Γ _G  ? Γ _H for some group H, then |G| = |H|. These suggest the question whether the latter property holds for all finite noncyclic groups.     

Super Connectivity and Super Edge Connectivity of the Mycielskian of a Graph

Mycielski introduced a new graph transformation μ(G) for graph G, which is called the Mycielskian of G. A graph G is super connected or simply super-κ (resp. super edge connected or super-λ), if every minimum vertex cut (resp. minimum edge cut) isolates a vertex of G. In this paper, we show that for a connected graph G with |V(G)| ≥ 2, μ(G) is super-κ if and only if δ(G) < 2κ(G), and μ(G) is super-λ if and only if G\ncong K₂{G\ncong K_2}.     

Non-Nilpotent Graph of a Group

We associate a graph 𝒩 _G with a group G (called the non-nilpotent graph of G) as follows: take G as the vertex set and two vertices are adjacent if they generate a non-nilpotent subgroup. In this article, we study the graph theoretical properties of 𝒩 _G and its induced subgraph on G \ nil(G), where nil(G) = {x ∈ G | ? x, y ? is nilpotent for all y ∈ G}. For any finite group G, we prove that 𝒩 _G has either |Z*(G)| or |Z*(G)| +1 connected components, where Z*(G) is the hypercenter of G. We give a new characterization for finite nilpotent groups in terms of the non-nilpotent graph. In fact, we prove that a finite group G is nilpotent if and only if the set of vertex degrees of 𝒩 _G has at most two elements.     

A note on unimodular congruence of the Laplacian matrix of a graph

Let G be a simple connected graph and L(G) be its Laplacian matrix. In this note, we prove that L(G) is congruent by a unimodular matrix to its Smith normal form if and only if G is a tree.     

On Commuting Automorphisms of Finite p-Groups with a Metacyclic Quotient

Let G be a finite non-Abelian p-group, where p is an odd prime, such that G/Z(G) is metacyclic. We prove that all commuting automorphisms of G form a subgroup of Aut(G) if and only if G is of nilpotence class 2.

     

Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge

Tutte proved that every 3‐connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth‐first‐search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3‐regular or if G does not contain two disjoint pairs of adjacent degree‐3 vertices.     

Free Group Actions on Spaces Homotopy Equivalent to a Sphere

For infinite-dimensional homotopy space forms X/G with G nontrivial finite cyclic groups, we study the homotopy type of X/G. We show that the Euler class of X/G is not zero if and only if X/G is finitely dominated.     

On the edge-coloring problem for a class of 4-regular maps

A (plane) 4-regular map G is called C-simple if it arises as a superposition of simple closed curves (tangencies are not allowed); in this case σ (G) is the smallest integer k such that the curves of G can be colored with k colors in such a way that no two curves of the same color intersect. We prove that if σ (G) ≤ 4, G is edge colorable with 4 colors. Moreover we show that a similar result for maps G with σ(G) ≤ 5 would imply the Four-Color Theorem.     

Diameter-vital edges in a graph

The graph resulting from contracting edge e is denoted as G/e and the graph resulting from deleting edge e is denoted as G − e. An edge e is diameter-essential if diam(G/e) < diam(G), diameter-increasing if diam(G − e) < diam(G), and diameter-vital if it is both diameter-essential and diameter-increasing. We partition the edges that are not diameter-vital into three categories. In this paper, we study realizability questions relating to the number of edges that are not diameter-vital in the three defined categories. A graph is diameter-vital if all its edges are diameter-vital. We give a structural characterization of diameter-vital graphs.     

Direct Sum of Distributive Lattices on the Perfect Matchings of a Plane Bipartite Graph

Let G be a plane bipartite graph and M(G){\cal M}(G) the set of perfect matchings of G. A property that the Z-transformation digraph of perfect matchings of G is acyclic implies a partially ordered relation on M(G){\cal M}(G). It was shown that M(G){\cal M}(G) is a distributive lattice if G is (weakly) elementary. Based on the unit decomposition of alternating cycle systems, in this article we show that the poset M(G){\cal M}(G) is direct sum of finite distributive lattices if G is non-weakly elementary; Further, if G is elementary, then the height of distributive lattice M(G){\cal M}(G) equals the diameter of Z-transformation graph, and both quantities have a sharp upper bound é\fracn(n+2)4ù\lceil\frac{n(n+2)}{4}\rceil, where n denotes the number of inner faces of G.     

An upper bound on the size of a largest clique in a graph

A graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point-determining graph is the set G^O of all vertices, v, such that G–v is point determining. In this paper we show that the size, ω(G), of a maximum clique in G satisfies ω(G) ? 2|π (G)^O|, where π(G) (the point determinant of G) is obtained from G by identifying vertices which have the same neighborhood.     

Groups whose vanishing class sizes are not divisible by a given prime

Let G be a finite group. An element ${g\in G}Let G be a finite group. An element g ? G{g\in G} is a vanishing element of G if there exists an irreducible complex character χ of G such that χ(g) = 0: if this is the case, we say that the conjugacy class of g in G is a vanishing conjugacy class of G. In this paper we show that, if the size of every vanishing conjugacy class of G is not divisible by a given prime number p, then G has a normal p-complement and abelian Sylow p-subgroups.     

Iterating the branching operation on a directed graph

The branching operation D, defined by Propp, assigns to any directed graph G another directed graph D(G) whose vertices are the oriented rooted spanning trees of the original graph G. We characterize the directed graphs G for which the sequence δ(G) = (G, D(G), D²(G),…) converges, meaning that it is eventually constant. As a corollary of the proof we get the following conjecture of Propp: for strongly connected directed graphs G, δ(G) converges if and only if D²(G) = D(G). © 1997 John Wiley & Sons, Inc.     

List‐coloring the square of a subcubic graph

The square G² of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G²) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G² equals the chromatic number of G², that is, χ_l(G²) = χ(G²) for all G. If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ(G) = 3 satisfies χ_l(G²) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ(G) = 3 other than the Petersen graph satisfies χ_l(G²) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 7, then χ_l(G²) ≤ 7. Dvo?ák, ?krekovski, and Tancer showed that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 10, then χ_l(G²) ≤6. We improve the girth bound to show that if G is a planar graph with Δ(G) = 3 and g(G) ≥ 9, then χ_l(G²) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008     

On a Class of P5-Free Graphs

A graph G is perfect in the sense of Berge if for every induced subgraph G′ of G, the chromatic number χ(G′) equals the largest number ω(G′) of pairwise adjacent vertices in G′. The Strong Perfect Graph Conjecture asserts that a graph G is perfect if, and only if, neither G nor its complement ? contains an odd chordless cycle of length at least five. We prove that the conjecture is true for a class of P₅-free graphs.     

On integral sum graphs with a saturated vertex

As introduced by F.Harary in 1994, a graph G is said to be an integral sum graph if its vertices can be given a labeling f with distinct integers so that for any two distinct vertices u and v of G, uv is an edge of G if and only if f(u)+f(v) = f(w) for some vertex w in G.     

Bounding the Derived Length of a Solvable Group: An Improvement on a Result by Gluck

Let cd(G) be the set of degrees of irreducible complex characters and dl(G) be the derived length of the finite group G. It is a result by Gluck that if G is solvable then dl(G) ≤2|cd(G)|. Using a result of Isaacs and Knutson, I will in this article show that this bound can be improved to dl(G) ≤2|cd(G)| ?3 when |cd(G)| ≥3.     

Entropy,Periodicity, and Graphs with Zero Euler Characteristic

Let G be a graph which contains exactly one simple closed curve. We prove that a continuous map f : G → G has zero topological entropy if and only if there exist at most k ≤ |(Edg(G) End(G) 3)/2] different odd numbers n1,...,nk such that Per(f) is contained in ∪i=1^k ∪j=0^∞ ni2^j, where Edg(G) is the number of edges of G and End(G) is the number of end points of G.