Eulerian properties of non-commuting and non-cyclic graphs of finite groups

ABSTRACTFor a non-abelian group G, the non-commuting graph Γ(G) has G−Z(G) as its vertex set and two vertices x and y are connected by an edge if xy≠yx. For a non-cyclic group G, the non-cyclic graph Γ′(G) has G−Cyc(G) as its vertex set, where Cyc(G) = {x|⟨x,y⟩ is cyclic, for all  y∈G} and two vertices x and y are connected by an edge if ⟨x,y⟩ is not cyclic. We show that for all finite non-abelian groups G, Γ(G) is eulerian if and only if Γ′(G) is eulerian. We investigate the eulerian properties of these graphs for various G showing, in particular, that Γ(G) (and hence Γ′(G)) is path-eulerian if and only if G≅S3.