0
$\begingroup$

I remember that I once read/heard that graphs may be given a shorthand notation when you

  1. take the upper diagonal of the adjacence matrix,
  2. put the resulting lines next to each other and
  3. convert the resulting binary number into hex,

or at least something like that.

Is there a more compact notation when you deal with bicubic graphs?

since you'll get plenty of 00...00 entries with an approach like the one above. I know about the LCF notation, but I would prefer one that also works for non hamiltonian graphs.

$\endgroup$
2
$\begingroup$

In the recent paper "Generation and Properties of Snarks" by Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund and Klas Markström the following method is used for cubic graphs:

They write: "The graphs in these appendices are given in the following format: Each list corresponds to an adjacency list for the graph where only higher numbered neighbours are listed. That is, first comes the neighbours of vertex 1, next the higher numbered neighbours of vertex 2 and so on."

e.g. {2, 3, 4, 5, 6, 7, 8, 9, 10, 7, 9, 8, 10, 11, 12, 13, 14, 15, 16, 15, 17, 18, 19, 18, 20, 18, 21, 22, 21, 23, 23, 24, 22, 24, 25, 26, 26, 25, 26} is the graph with edges {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {3, 7}, {3, 8}, {4, 9}, {4, 10}, {5, 7}, {5, 9}, {6, 8}, {6, 10}, {7, 11}, {8, 12}, {9, 13}, {10, 14}, {11, 15}, {11, 16}, {12, 15}, {12, 17}, {13, 18}, {13, 19}, {14, 18}, {14, 20}, {15, 18}, {16, 21}, {16, 22}, {17, 21}, {17, 23}, {19, 23}, {19, 24}, {20, 22}, {20, 24}, {21, 25}, {22, 26}, {23, 26}, {24, 25}, {25, 26}}

A cubic graph where all 2-factors only consist of odd cycles

$\endgroup$
1
0
$\begingroup$

Often posting a question here, brings the brain back on track.

Since the graph is bipartite, one could

  1. anti-block-diagonalize the adjacence matrix and
  2. use the procedure described above on, let's say, the upper left block

this would give a much denser, less redundant notation.

Other answers are still welcome...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.