Conference rusure::math

F'rinstance, a place to start is to show that a regular edge-but-not-vertex-
transitive graph must be a subgraph, G, of K(n,n), for some n, where G has
2n vertices.

Regards,
Andrew.

	Define edge-transitive, vertex-transitive, and regular. :-)

	I know what you mean by graph and bipartite graph K(a,b):

		graph:	an ordered pair of sets (V,E) where elements
			of E (edges) are unordered pairs of elements
			of V (vertexes or vertices).

		complete graph K(n):	a graph (V,E) where V has n
			elements and E contains every unordered pair
			from V.

		bipartite graph K(n,m):	a graph (V,E) where V is a
			disjoint union of V1 and V2, where V1 has n
			elements, V2 has m elements, and E contains
			every unordered pair of an element of V1 and
			an element of V2 (and only those pairs).

	Dan

	Thanks for the definitions and the correction, Andrew.

>>	The bipartite graph K(a,b) is an example of a graph which is edge-
>> transitive but not vertex-transitive.   Can you find a *regular* graph
>> which has this property?   (I'm told there are some.)

	Can you give us a hint?  Like a minimum number of vertexes
	under which we shouldn't bother to look?

	Dan

>	Can you give us a hint?  Like a minimum number of vertexes
>	under which we shouldn't bother to look?

	Well, the first step is to look at .1, which restricts enormously
the kinds of graph that could have this property.   Then it's pretty
obvious that the number of vertices must be at least 12.   I don't know
anything about the solution, except that it is "not at all easy to
find" these graphs.

	I would suggest toying with graphs with additional constraints:
eg: bipartite with vertex set partitioned into L & R, such that each vertex
in L has a twin, also in L, with exactly the same neighbours.   But no
vertex in R has this property.   If you can do this edge-transitively, then
you're home.

Regards,
Andrew.

>	I would suggest toying with graphs with additional constraints:
>eg: bipartite with vertex set partitioned into L & R, such that each vertex
>in L has a twin, also in L, with exactly the same neighbours.   But no
>vertex in R has this property.   If you can do this edge-transitively, then
>you're home.

	Along the lines above, I've come up with *a* solution, on 24 vertices
with degree 4.

	Let the vertices in L be l_1,...,l_6, m_1,...,m_6.   Then let (i,j) 
denote that there is a vertex in R adjacent to l_i, l_j, m_i & m_j.   Our
graph is defined by the list of all 15 possible pairs (i,j) *except*:

	(1,2), (3,4), (5,6)

	This satisfies all the requirements, I think.

	Question: is there an solution on a smaller number of vertices?

Regards,
Andrew.

>	Question: is there an solution on a smaller number of vertices?

	Yes, there's one on 20 vertices, also I've located solutions of
order 32 and 36.

	Let me try to generalize a little the construction that I'm
using here.

	If I have a vertex-transitive *and* edge-transitive graph, G, of order 
g, and degree 4, then I can build an edge-transitive but *not* vertex-transitive
regular graph, G', of order 4*g, and degree 4.

	I label the vertices of G as 1,...,g and the vertices of G' as
l_1,...,l_g, m_1,...,m_g, r_1,...,r_(2*g).   I label the edges of G 1,...,2*g.
Then if edge e of G links i to j, this determines that in G', r_e is adjacent
to l_i, l_j, m_i and m_j.

	Now, building suitable G is not too difficult.

	For g = 5, K5 does the job.
	For g = 6, K(2,2,2) (complete tripartite) gives the solution in -.1
	For g = 7, there is no such graph.
	For g = 8, K(4,4)
	For g = 9, imagine 9 vertices in a 3-by-3 torus.   a links to b iff
they are either in the same row or the same column.

Questions abound:

	(1) can we do better than 20 as the minimum solution?
	(2) can we show there are an infinite number of connected 4-regular 
edge-transitive graphs?
	(3) what about degree 3 graphs?

Regards,
Andrew.