Related Links (Outside this Site)

Wikipedia :   Tensor product of graphs   |   Petersen graph

---

(2008-06-26)   Adjacency Matrix
A concept which is usefully generalized beyond simple graphs.

A  directed graph  (or  digraph)  is a set of nodes connected by directed edges.  In a  simple  digraph, there's  at most one  such edge from one node to the other  (for non-simple digraphs, there can be several).  Some authors do not allow  loops  (edges which go from one node to itself)  in a  simple  graph.

A digraph,  simple or not,  is fully specified by its so-called  adjacency matrix  whose element  a_ij  is equal to the number of edges going from node  i  to node  j.

Normally, the adjacency matrix of a digraph is a square matrix of nonnegative integers.  However, we may also usefully consider  rectangular  matrices  in the case of  bipartite graphs  where the departure nodes and arrival nodes of the edges are from disjoint sets.  Note that a  bipartite graph  is also defined as a special type of  undirected  graph whose nodes can be divided into two disjoint sets U and V such that every [undirected] edge of the graph connects one node of U to one node of V.  Either viewpoint defines in terms of graphs a structure isomorphic to the  relations  between U and V  (fundamentally, a  relation  is a subset of the Cartesian product U´V).

Also, egdes could be labeled with additive  amplitudes  different from 0 or 1.  If several edges [having the same origin and target] are equated with a single edge carrying an amplitude equal to the sum of their amplitude,  we obtain a mathematical structure isomorphic to the unrestricted matrices over the set of amplitudes.  Amplitudes can be real or complex numbers, or any other type of quantity for which addition is well-defined  (cf. quantum mechanics).

The digraph (or the bipartite graph) whose adjacency matrix is the  product of two adjacency matrices turns is simply the digraph in which tere are as many edges from node i to node j as there are ways to go from i to j using one edge of the first graph [to go from i to any node k] and one edge of the second [to go from k to j].

Indeed, if there are  a_ik  ways to go from i to k and b_kj  ways to go from k to j, then the number of ways to go from i to j via all possible nodes k is given by the following formula, which is also how the relevant element in the product of the adjacency matrices is computed:

å _k   a_ik  b_kj

Applying this remark iteratively, we see that the matrix  Aⁿ  is the adjacency matrix of a digraph which has as many edges from i to j as there are paths from i to j consisting of n edges of the graph whose adjacency matrix is  A.

This result was put to good use by  Max Alekseyev  in the following solution of an enumeration problem originally posed by  Philip Brocoum.

---

(2008-06-27)   Brocoum's Silent Circles
Screaming circles  enumerated by  Max Alekseyev.

On 2008-06-13,  Max Alekseyev  sent a complete outline of the following solution to the problem originally posed by Philip Brocoum, whereby it is asked in how many different ways  2n  people in a circle can avoid eye contact if they must look left, right, or directly across the circle.  (The names "screaming circles" and/or "silent circles" come from the fact that this activity has actually been practiced with the dramatic rule that two people who make eye contact must both  scream.)

Consider the 8 possible ways that two diametrically opposed people may gaze without looking at each other:  

Let  G  be the digraph whose vertices are those  8  configurations,  where an edge from i to j indicates that, if the pair j is next to i in the counterclockwise direction, then eye contact occurs neither between the respective "top" members of pairs nor between the bottom members.  The  adjacency matrix  A  of the digraph G is:

	1	0	1	1	1	0	1	0
	0	1	1	1	1	0	0	1
	0	1	1	1	1	0	0	1
	1	0	1	1	1	0	1	0
	0	0	1	1	1	0	0	0
	1	1	1	1	1	1	1	1
	1	1	1	1	1	1	1	1
	1	1	1	1	1	1	1	1

The 8 highlighted locations correspond to pairs of configurations obtained from each other by a  180° flip  (half-turn rotation).  A full  silent circle  of  2n  people  (n>1)  is equivalent to a path of n edges of G going from one node to its flipped counterpart.  The number of all such silent circles is thus the sum of all highlighted elements in the n-th power of the above adjacency matrix, starting with:

Now, the characteristic polynomial of the matrix A is:

det ( xI - A )   =   x ⁴  ( x - 1 )  ( x ³ - 7 x ² + 9 x - 1 )
=   x ⁴  ( x ⁴ - 8 x ³ + 16 x ² - 10 x + 1 )

By the Cayley-Hamilton theorem,  A  is a root of the above polynomial.  Thus, the successive matrix elements at a given location in the n-th powers of  A  satisfy the following linear recurrence  (for n>3).  So does any sum of such elements.

a_n+4   =   8 a_n+3  -  16 a_n+2  +  10 a_n+1  -  a_n

In particular, the sum of the elements of  Aⁿ  for the locations highlighted above satisfy this recurrence and the sequence is fully defined by stating that it starts with  2, 6, 30 and 156  (corresponding respectively to  n = 0, 1, 2 and 3).

For  n = 0,  we're indeed dealing with 2 highlighted nonzero elements in the identity matrix  I.  For  n = 1,  we have  6  nonzero highlighted elements in  A.  The other two terms are from the sums of the relevant elements in the square and the cube of  A, as given above. 

The cases  n = 0  and  n = 1  are part of a valid basis for the solution sequence but are not relevant to Brocoum's original problem, which arguably starts with a circle of 4 people  (the above analysis is not valid for a "circle" of only two people):

That sequence  also  obeys a  third order  recurrence  (cf. A141385) :

a_n+3   =   7 a_n+2  -  9 a_n+1  +  a_n  -  2

30, 156, 826, 4406, 23562, 126104, 675074, 3614142, 19349430, 103593804, 554625898, 2969386478, 15897666066, 85113810056, 455687062274, 2439682811478, 13061709929934, 69930511268508, 374397872321626, 2004472214764742, 10731655163727066, 57455734085528408, 307609714339920002, 1646898048773411406, 8817254646440128230, 47206309800460114956, 252735774834033062026, 1353110890280530527806, 7244360568257876251362, 38785261740114392071304, 207650697956760388764674, 1111731890604551068962342, 5952052214361128375925630, 31866429183043699399583004, 170608266242660291482712698, 913412053265589874158667478, 4890276405858230195165841066, 26181834627859962790215592856, ...

Against my  feeble  advice, Alekseyev chose to put this sequence on record  (as A141221)  with a dubious start at  n = 1  with value 0  (to include the degenerate case of a "circle" of  2  people who have no choice but to look at each other).

---

(2008-06-28)   Silent Prisms
A screaming game for  short-sighted  people.

Before generalizing Brocoum's poser, let's present  another version  of the screaming game which can be analyzed with the  same  tools...

Consider a "prism" of 2n people.  They are arranged in two concentric circles so that each person in the inner circle faces directly a "partner" in the outer circle and vice-versa.  Each person is allowed to look at one of three people; the "partner" on the other circle or either neighbor on the  same  circle.

This screaming game accomodates short-sighted people, as each person will only look at nearby people, even with large circles.     Similarly, we could allow people to look only at the  other  circle; that's to say at the partner or to the left or right of that partner.  Such rules just yield a screaming game isomorphic either to Brocoum's circle  (if n is odd)  or to the same prism we're now discussing  (if n is even).

The problem of enumerating the number of ways 2n people can avoid eye contact under such rules can be dealt with exactly as above, with the  same digraph  G,  except that the nodes of  G  bear different labels, using the following  8 symbols associated with each pair of  partners.  The top of the symbol indicates what direction the partner in the  inner  circle is looking at  (right = counterclockwise)  whereas the bottom of the symbol tells about the parner in the  outer  circle.  (A vertical arrow thus indicates that one partner is looking at the other.  No symbols have two vertical arrows because partners can't look  silently  at each other).

By convention, if  j  is in the location next to  i  in the   counterclockwise  direction,  then there's an edge from node  i  to node  j  in our digraph  G  iff  there no eye contact on either circle involving the two pairs of partners  This statement depends only on the node labels if we assume that each circle contains at least 3 people  (that's a more severe restriction than for the previous analysis, which remained perfectly valid even for  n = 2).  This yields the following adjacency matrix, where diagonal elements are now "highlighted" to indicate that a  silent solution  is a circuit of n edges from one node  back to itself  (no "flipping").

	1	0	1	1	1	0	1	0
	0	1	1	1	1	0	0	1
	0	1	1	1	1	0	0	1
	1	0	1	1	1	0	1	0
	0	0	1	1	1	0	0	0
	1	1	1	1	1	1	1	1
	1	1	1	1	1	1	1	1
	1	1	1	1	1	1	1	1

This adjacency matrix is exactly the one we met before.  So, Alekseyev's recurrence holds between its successive powers  (at least beyond the fourth power)  and, therefore, between the sums of the highlighted elements, which are now actually the  traces  of those powers of  A,  namely  (A141384) :

8, 8, 32, 158, 828, 4408, 23564, 126106, 675076, 3614144, 19349432 ...
a_n+4   =   8 a_n+3  -  16 a_n+2  +  10 a_n+1  -  a_n

The recurrence, which was  a priori  guaranteed only for  n>3  happens to hold down to  n = 1  (it would hold for  n = 0  with a value of  4,  instead of 8).  So, we are slightly less  lucky  than in the previous case.  For  n > 0, an explicit formula is:

a_n   =   Aⁿ + Bⁿ + 1 + Cⁿ     where:
A   =   5.3538557854308282...   =   ( 7 + 2 Ö22 cos u ) / 3
B   =   1.5235479602692093...   =   ( 7 - Ö22 cos u  + Ö66 sin u ) / 3
C   =   0.1225962542999624...   =   ( 7 - Ö22 cos u  - Ö66 sin u ) / 3
with   u  =  ¹/₃  Arctg ( Ö5319 / 73 )
The sequence also obeys a simpler  third order  recurrence  (cf. A141385) :

a_n+3   =   7 a_n+2  -  9 a_n+1  +  a_n  +  2

As previously, the beginning of the sequence does not correspond to actual enumerations  (even more so, since the above is only valid if  n  is 3 or more).  The proper enumerations start with the numbers  158, 828 and 4408, which appear in that capacity within the more general discussion of the following section.

Note, in particular, that 4 people can be arranged in a proper screaming circle  (the corresponding graph is a tetrahedron, for which 30 of the 81 configurations are silent ones)  but not in a screaming prism, which requires at least 6 people  (as noted above, the value of  32,  which appears in the sequence of traces for  n = 2,  is irrelevant to screaming tallies).  2 people can't play any screaming game.

All told, with  2n  people, there are always just two more silent configurations in a screaming game with a double circle (the above "prism" type) than in an ordinary game where "partners" are opposite each other in a single circle:

2n	4	6	8	10	12	14	16	18
Single	30	156	826	4406	23562	126104	675074	3614142
Double		158	828	4408	23564	126106	675076	3614144

---

(2007-03-19)   Brocoum's Poser Generalized
Markings of one edge per node in which no edge is marked twice.

There are  d  ways to mark only one edge at a node of degree d.  The total number of unrestricted markings is simply the product of the degrees of all nodes.  Among those, we want to enumerate the markings for which no edge is marked twice  (once at each of its extremities).

Philip Brocoum posed a special case of this problem (2007-03-10; e-mail) after pondering it for more than a year (2006-01-26).

One lesser generalization of Brocoum's poser is to consider  married people in a circle where no two spouses are neighbors, with the rule that one person may only look at a neighbor or a spouse  (Brocoum's original puzzle considered a circle of 10 people, with spouses always sitting at opposite locations across the circle).  We want to enumerate the scenarios where nobody makes eye contact.

In technical terms, this is a restriction of our general problem to undirected cubic Hamiltonian graphs  (namely, graphs where 3 edges meet at each node and which allow a circuit that goes through every node once and only once).

This class of graphs is complex enough to make questions about them about as difficult as they are for unrestricted graphs.

With 4 nodes, there's only one such graph  (the regular tetrahedron)  in which there are 30 different satisfactory markings  (out of 81 unrestricted possibilities). 

With 6 nodes, Hamiltonian cubic graphs have 729 possible markings (3⁶ ).  Two configurations lead to different numbers of satisfactory markings  (156 or 158).

With 8 nodes, there can be  826, 828, 834, 842 or 860 satisfactory markings.  (Two disjoint tetrahedra form a  disconnected  8-graph allowing 900 markings.)

Note that the leftmost of the above graphs is isomorphic to the Brocoum case  (where two spouses are always in diametrically opposed positions).  To prove this, you may want to look for a Hamiltonian circuit besides the "obvious" outer circle and redraw the graph accordingly.  (Numbering the nodes helps!).

For the 17 Hamiltonian cubic graphs with 10 nodes, we obtain 17 different tallies of satisfactory markings:  4384, 4392, 4406, 4408, 4416, 4438, 4446, 4456, 4476, 4484, 4494, 4502, 4526, 4530, 4556, 4600 and 4602.

Disconnected cubic graphs with 10 nodes allow either 4680 or 4740 markings  (30 tetrahedral configurations and either 156 or 158 for the other 6 nodes).  We're leaving out the only two connected cubic graphs with 10 nodes which are not Hamiltonian  (namely, the Petersen graph and the bridged graph   ).

Non-isomorphic graphs with the same tally exist, since the 80 Hamiltonian 12-node cubic graphs yield  only  75  tallies:

23248, 23256, 23294, 23310, 23348, 23356, 23358, 23372, 23376, 23404, 23412, 23436, 23450, 23466, 23468, 23522, 23562, 23564, 23592, 23608, 23616, 23626, 23644, 23654, 23662, 23710, 23718, 23726, 23734, 23772, 23788, 23816, 23842, 23868, 23878, 23904, 23922, 23930, 23950, 23968, 23972, 23976, 23984, 23992, 23994, 24022, 24032, 24038, 24076, 24078, 24094, 24108, 24130, 24144, 24164, 24190, 24222, 24226, 24236, 24272, 24274, 24318, 24356, 24380, 24382, 24470, 24516, 24578, 24588, 24598, 24628, 24632, 24640, 24848, 25200.

A trivial Hamiltonian circuit for an n-gonal prism  (a cubic graph with 2n nodes)  is obtained from a clockwise circuit of the top polygon and a counterclockwise circuit of the bottom polygon by replacing the two horizontal edges of one face with the two vertical edges of that face.

The numbers of  cubic graphs  with 2n nodes is given by the following sequence.  This includes the empty graph  (for n = 0)  but no 2-node graph  (for n = 1) :
1, 0, 1, 2, 6, 21, 94, 540, 4207, 42110, 516344, 7373924 ... (A005638).

The numbers of  connected cubic graphs  with 2n nodes are:
1, 0, 1, 2, 5, 19, 85, 509, 4060, 41301, 510489, 7319447 ... (A002851).

The numbers of Hamiltonian cubic graphs  with 2n nodes  are:
1, 0, 1, 2, 5, 17, 80, 474, 3841, 39635, 495991, 7170657 ... (A001186).

For very large numbers of nodes,  almost all cubic graphs are Hamiltonian  (a result established in 1992 by R.W. Robinson & N.C. Wormald).

Here are a few pretty representations of some  [Hamiltonian]  cubic graphs with the associated tallies of their numbers of silent configurations:

30	158	828	842
2n = 4	2n = 6	2n = 8

23564	24470
2n = 12		2n = 20

2n = 24

---

(2008-07-17)   Line Graph
A graph  L(G)  whose vertices are the edges of another graph  G.

Let  G  be a graph,  V  its set of vertices and  E  its set of edges.  The so-called  line-graph  of  G  is the graph  L(G)  whose set of vertices is  E  and whose edges connect all pairs of E which have one common extremity in G.

---

(2008-07-14)   Vertex Transitivity.  Edge Transitivity.
A  symmetric graph  is  both  vertex-transitive  and  edge-transitive.

A  graph automorphism  of a  simple  graph  G  is a bijection  f  of its vertices such that the image  f (e) = { f (i), f (j) }  of any edge  e = {i,j}  is always an edge.

A graph is said to be  vertex transitive  when, for any two of its vertices  i  and  j,  there is an automorphism which maps  i  into  j.

A simple graph is said to be  edge transitive  when, for any two of its edges u  and  v,  there is an automorphism which maps  u  into  v.

A simple graph is  symmetric  when it's both vertex-transitive and edge-transitive.

A simple graph which is edge-transitive but  not  vertex-transitive is said to ne  semisymmetric.  Such a graph is necessarily  bipartite.