The power graph revisited

In response to a question from Ghodratollah Aalipour in Tehran, I have been thinking again about the power graph of a group. This is the graph whose vertices are the group elements, two vertices being joined if one is a power of the other.

I can prove:

Proposition. The clique number of the power graph of any group is at most countably infinite.

The proof is not difficult. Let C be a clique containing the element x. Then we can divide the rest of C into two parts: elements y such that y=xn; and elements y such that x=yn. The first part is obviously countable. For the second, we show that the set of such elements with any fixed value of n is finite, from which the result will follow. If x=yn=zn and y and z are joined (so one is a power of the other), a short calculation shows that y and z generate the same, finite, cyclic group, and we are done.

Aalipour and his colleagues had proved that if G has exponent n, then its clique number is at most n, and had asked me whether the same is true for the chromatic number. (Indeed, it is.) But this suggests an open problem:

Problem. Is it true that the chromatic number of the power graph of any group is at most countably infinite?

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems. Bookmark the permalink.

5 Responses to The power graph revisited

  1. Dear Peter,

    I would like to draw your attention to a graph –called the Non-cyclic graph of a group– which I and my colleague –A. Mohammadi Hassanabadi– has introduced in
    [1] A. Abdollahi and A. Mohammadi Hassanabadi, Non-cyclic graph of a group, Communications in Algebra, 35 (2007) 2057-2081.

    and we have also studied it in

    [2] A. Abdollahi and A. Mohammadi Hassanabadi, Non-cyclic graph associated with a group, Journal of Algebra and Its Applications, 8 No. 2 (2009) 243-257.

    The non-cyclic graph of a group non-locally cyclic group G is a graph whose vertex set is G-Cyc(G) (where Cyc(G) is the set of all elements x of G s.t. is cyclic; this is a subgroup of the center) and two vertices are adjacent whenever they generate a non-cyclic subgroup.

    The subgraph of the power graph of a non-locally cyclic group G on the set G-Cyc(G) is an spaning subgraph of the non-cyclic graph of G.

    Whenever G is a non-cyclic group in which every element has a power of a prime order (e.g., G is of prime power order) then the induced subgraph of the power graph of G on G-Cyc(G), is exactly the non-cyclic graph of G.

    Theorem 4.2 of [1] is about a characterization of group whose non-cyclic graph has a finite clique number; this is a B.H.Neumann’s like characterization for Paul Erdos problem on Non-commuting graph

    Proposition 4.6 (1) of [1] gives a characterization of groups whose non-cyclic graph has no infinite indepemdent set.

    Proposition 4.6 (2) of [1] says that
    The independence number of G is finite if and only if the exponent of G is finite. In this case, the independece number of the non-cyclic graph is explicity is given.
    The latter result is apparently very similar to the one of Ghodratollah and his colleagues concerning the power graph.

    The chromatic number and clique number of the non-cyclic graph of a finite noncyclic group are the same. This is a part of Theorem 4.7 of [1].

    There are many results and open problems in [1] and [2].

    So it may be interesting to find a `good’ relation between these two graphs.

    Best Regards
    Alireza Abdollahi

    • Dear Alireza: Thanks very much for this. I will certainly come back to it! But there is something missing from your definition. “all elements x of G s.t. is cyclic” – is this the centralizer of x, or what?

  2. Dear Peter,

    Sorry.

    The “cyclicizer” of a group G, denoted by Cyc(G), is the set of all elements x of G such that is cyclic for all y in G.
    This is a subgroup of the center of G.
    If the group is finite, its cyclicizer is a cyclic subgroup of the center.

    I am looking forward your coming back.
    Best Regards
    Alireza

  3. Sorry again.
    It is somehow curios; The math equation will not publish!! As it has a preview mod then it will not happen; Sorry for this; I am a very beginner to send messages in wordpress!

    Anyway, the definition of the cyclicizer of a group G is as follows without using any math symbol:
    the set of elements x of G such that the two-generated subgroup generated by x and any other element y is cyclic for all y in G.

    Best Regards

    • The trouble with WordPress is that it recognises some commands and not others. I managed to make it recognise angle brackets in a posting, but the rules for comments are a bit different.

      Here goes:

      the set of elements x of G such that ⟨x,y⟩ is cyclic for all y in G.

      That seems to work!

      The commands for the angle brackets are ⟨ and ⟩

      By the way, I make a lot of use of the webpage http://www.digitalmediaminute.com/reference/entity/index.php which has HTML code for many mathematical symbols.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s