| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
An isomorphism of a graph onto itself is known as an automorphism.
Two points u and v of a graph are similar if there is an automorphism
of the graph that takes u into v. A graph is called point symmetric
if every pair of points are similar.
Here are some conjectures.
C1. Every connected point symmetric graph of more than two points
contains a Hamiltonian curcuit.
C2. Let d(i) be the number of points at distance i from a point in a
connected point symmetric graph G. Then the values d(i) uniquely
determine the graph G.
The above are also conjectured (C3 and C4) for directed connected point
symmetric graphs.
Any proofs, suggestions, or counterexamples would be appreciated.
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 53.1 | TOOLS::GILBERT | Sat Jan 25 1986 21:20 | 1 | ||
See note 425 and following for a counter-example to C2. | |||||
| 53.2 | the ubiquitous Petersen | HERON::BUCHANAN | combinatorial bomb squad | Wed Jul 11 1990 17:24 | 16 |
Counter-example to C1: The Petersen graph on 10 nodes. Label them a1-a5,b1-b5. Link ai to bi, for all i, ai to a(i+1), for all i mod 5, and bi to b(i+2) mod 5. This is connected and "point-symmetric", whilst it is the work of moments to demonstrate that no Hamiltonian cycle exists. This is such a simple example that I find it hard to buy Jerry Leichter's remark that this stumped the graph theoreticians at Yale. (see 425.5) Replacing each edge by a pair of directed edges gives a similar result for C3. Regards, Andrew. | |||||
| 53.3 | GUESS::DERAMO | Colorado Rocky Mountain high | Wed Jul 11 1990 20:15 | 3 | |
But in 425.7 you say they must have Hamiltonian cycles! Dan | |||||
| 53.4 | propositional calculus 101 | HERON::BUCHANAN | combinatorial bomb squad | Thu Jul 12 1990 09:33 | 11 |
> But in 425.7 you say they must have Hamiltonian cycles! No, I don't. I say Cayley => point-symmetric (true) & Cayley => Hamiltonian (I'm less sure about that now). Petersen is point-symmetric but it is not a Cayley graph! Regards, Andrew. | |||||
| 53.5 | GUESS::DERAMO | Colorado Rocky Mountain high | Thu Jul 12 1990 15:06 | 24 | |
>> > But in 425.7 you say they must have Hamiltonian cycles! >> >> No, I don't. >> >> I say Cayley => point-symmetric (true) >> & Cayley => Hamiltonian (I'm less sure about that now). >> >> Petersen is point-symmetric but it is not a Cayley graph! Oops. I had read >> The "point-symmetric" graphs that come out of the disk-flipping >> problem are simply the Cayley diagrams for the underlying abstract >> groups. as << The "point-symmetric" graphs ... are simply the Cayley diagrams << for the underlying abstract groups. I.e. as point-symmetric => Cayley, which when combined with Cayley => Hamiltonian results in what I said you said. Dan | |||||