Re: Switching of graphs


Hello again. Some more results. Now with sketches of proofs

1) First a faster construction that doesn't need contractions too.
The final graph is SWT(n), for n=1, 2, 3, ...

i) Consider V={1,2,...n}
ii) The vertices of SWT(n) are the all subsets of V of size at most
floor(n/2) *
iii) Let A be a vertex of SWT(n).
a) if 0< |A|: For each v in A create an edge joining
A to A\{v}
b) if |A| < floor(n/2): For each v in V\A create an edge
joining A to A U {v} if
c) if |A| = floor(n/2) is odd: for each v in V\A create
an edge joining A to (V\A)\{v}

proof: in the end

2) Say that vertex A is of type 0 < t < floor(n/2) if A has t
elements. It means, a vertex in SWT(G) originated by t
switchings in G. A={} is of type 0. Then

i) v is of type 0: then v has exactly n neghbours of type 1
and no others
ii) v is of type 0 < t < floor(n/2) : then v has exactly t
neighbours of type (t-1) and n-t neighbours of type t+1
and no others
iii) v is of type floor(n/2):
a) floor(n/2) is even: then v has exactly floor(n/2)
neighbours of type floor(n/2)-1 and no others.
b) floor(n/2) is even: then v has exactly floor(n/2)
neighbours of type floor(n/2)-1 and exactly
n-floor(n/2) neighbours of the same type,
floor(n/2). And no others.

proof: follows directly from the construction in 1)

3) If n is even then SWT(n) is (n/2)-partite.

proof: This follows directly from 2

4) SWT(n) has 2^(n-1) vertices and is n-regular.

proof: follows directly from 1) and 2)

5) vertices of the same type are all similar. It means, if A and B
are of the same type then there exists an automorphsm
mapping A in B.

Proof: any permutation of {1...n} such that the image
of restriction to A is equals to B.

6) Let (A1,B1) and (A2,B2) be two pair of vertices in SWT(n),
not necessarily edges. If |A1 \cap B1| = |A2 \cap B2|
then both pairs are similar. It means there exists an
automorphism mapping A1 to A2 and B1 to B2.

Proof: any permutation of V such that the image of
restriction of the domain

i) to A1 \cap B1 is equal to A2 \cap B2
ii) to A1 \ (A1 \cap B1) is equal to A2\ (A2 \cap B2)
ii) to B1 \ (A1 \cap B1) is equal to B2\ (A2 \cap B2)


Now the proof of 1)

Let G be a labeled Graph with vertex set {1...n}.
Let S_v denote the labeled star in n vertices in which v is the
center, i.e the edge set of S_v is {(v,i): 1<= i <= n and i!=v}.

So the switching of vertex v in G can be viewed as the operation:

G xor S_v

where "xor" denotes the disjoint union of graphs. Or a bitwise
xor in
the adjascence matrix of the graphs.

If we switch 2 vertices u and v we have

G xor S_u xor S_v

So switching is comutative and associative. We can then
represent the graph in which a set A={u,v,w ...} by G_A
Before proceeding, denote the complement of a set of
vertices A as not A.

7) Theorem: G_A =G_notA

sketch: each pair (u,v) appears in exactly two star graphs:
S_u and S_v. The switching of a set A of vertices, counts the
parity of appearences of an edge in the stars S_k for k in A.
If both stars in wich the edge appears are in A, its parity will
be 0 and so it will be in the complement of A because no
star with this edge will be there. If The edge appears only
once in A, then it will appear exactly once in not A as well.
To finish, it doesn't matter if the edge appears or not in G
because it will afect in the same way both parities of
A and not A.

Now by definition of your graph, you join G_A to G_B if they
differ by a switching, it means, one element. But joinig
G_A to G_AU{v} is equal to join G_A to G_notA\{v} by
7). So we need only to consider the subsetsof V with at most
floor(|V|/2) elements. This completes the proof.

.

Relevant Pages

  • Re: Switching of graphs
    ... Let G be a graph. ... Switching a vertex v of G is the operation that ... By symmetry, we may assume G is the empty graph on n vertices ... If n is even, then Sis bipartite. ...
    (sci.math)
  • Re: A little challenge for relativists.
    ... Out of context graph of some data... ... > dependent, distant star, elliptical orbit. ... > So the rotational speed of a mirror is 2pi/t radians/sec ...
    (sci.physics.relativity)
  • Re: Switching of graphs
    ... The switching operations are involutions, ... The graph you describe is thus ... described as the edge graph of the -cube plus edges connecting ... each pair of antipodal vertices, or as the edge graph of the n-cube ...
    (sci.math.research)
  • Switching of graphs
    ... I have a question about switching. ... Let G be a graph. ... If we connect the graphs in a switching class according to the way they ...
    (sci.math)
  • Switching of graphs
    ... I have a question about switching. ... Let G be a graph. ... If we connect the graphs in a switching class according to the way they ...
    (sci.math.research)