6
$\begingroup$

Is there any way to generate all 4-regular plane graphs with 21 vertices, 8 faces of degree 3, and 15 faces of degree 4? If so, how many of these graphs are there and what are they?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

Brinkmann and McKay's program plantri can generate planar quadrangulations, which are planar graphs with all faces of size 4.

If you generate these on 23 vertices and then filter to keep only those of minimum degree 3 and maximum degree 4 then you will have the dual graphs of what you want.

It took a couple of seconds and produced about 20 graphs (can’t remember exactly).

You may have to check carefully that assumptions about connectivity and the plane/planar distinction match what you want.

Added Details

I just did

plantri -q -g 23 | pickg -d3 -D4

The options on plantri are -q for "quadrangulations" and -g for "graph6 format".

Then pipe the output into pickg and ask for minimum degree 3 and maximum degree 4.

This produces 23 graphs in under a second.

Then find their planar duals - SageMath can do this and is convenient for visualising them anyway.

Here is the list that I obtained, one graph per line, where I have just concatenated the entries of the adjacency matrix to form one long 0/1-string.

010110010000000000000101011000000000000000010101100000000000000101000110000000000000110000001100000000000011000000110000000000001100000011000000000100100001001000000000000010010000110000000000011000000011000000000001100000001100000000000110000100100000000000001001000011000000000001100000001100000000000110000000110000000000011000010010000000000000100100011000000000000110000101000000000000011001001000000000000001110001000000000000000011110
010110000010000000000101001100000000000000010100011000000000000101000000101000000000100001000010100000000010010000000110000000010000010000011000000001000100000001100000001000000100000110000000100001001000010000100010000001000001000000100000110000000100000011000000000001010000001100000001000010000000110000010000001000000011000000010001000000001100000100100000000000010100000110000000000001000011001000000000000110001001000000000000001100110
011100100000000000000101110000000000000000110001010000000000000110010001000000000000010101000100000000000001010000011000000000100000011000100000000001000100001010000000000100100100001000000000010001010001000000000001000100000110000000001010000000011000000000100000011000100000000010000100001010000000001100100100000000000000010001010100000000000011000100001000000000001010000011000000000000100100011000000000000010001101000000000000000011110
010110010000000000000101011000000000000000010101100000000000000101000101000000000000110000000110000000000011000000011000000000001100000001100000000100000001100010000000000100010000101000000000010010000000110000000011000000000011000000001100000100001000000000101001000000100000000010000001100010000000001000010000110000000000100010010010000000000110000100001000000000011000000101000000000000101001001000000000000011100001000000000000000011110
010110000100000000000101001100000000000000010100011000000000000101000001010000000000100001000001100000000010010000000011000000010000010000001100000001000100000000011000001100000010000001000100000000011000000100000100001100000001000000010000100100000010000010000001010000001000001000000101000001000001100000010100000000000100000001010001000000010000000100110000000011010000000100000000000100000011010000000000001000010101000000000000110100010
010110000100000000000101011000000000000000010100110000000000000101000001100000000000110000000011000000000010000100001100000000001001000000011000000001000001000001100000000100010110000000000100100001010000000000000010001100000100000000011000000000110000000001000000010011000000000100000100001100000000110000000000110000000010011000000010000000000001100000011000000000000110000101000000000000011001001000000000000001110001000000000000000011110
010110000010000000000101001100000000000000010100011000000000000101000000101000000000100001000000110000000010010100000001000000010001010000001000000001000101000000100000001000010100000010000000100001001000010000100000000001100001000000100000110000000100000010000010000001010000010000000001000011000001100000010100000000000010000001010001000000001100000100100000000000010100000110000000000001000011001000000000000110001001000000000000010100110
010110000010000000000101001100000000000000010100011000000000000101000000110000000000100001000001100000000010010000000110000000010000010000011000000001000100000000110000001000000100000010100000100001010000001000100100000101000000000000010000010100001000000011000001000000010000001100000001000010000000100000010100001000000010000001010001000000011000000100100000000000101000000110000000001000000011001000000000000110001001000000000000001100110
010110000100000000000101011000000000000000010100110000000000000101000001100000000000110000000110000000000010000100011000000000001001000000110000000001000001000011000000000100010011000000000100110000010000000000000011001100000000000000001001000101000000000000100001000110000000000110000000011000000000010001000101000000000000000101000110000000000000110000011000000000000011000101000000000000000101011000000000000000110101000000000000000011110
010110000100000000000101001100000000000000010100011000000000000101000001010000000000100001000101000000000010010000000110000000010000010000011000000001000100000000110000001100000000000011000100010000010000000100000100000100000001100000010000000100000110000001000001010000010000001100000101000000000000100000010100010000000010000001010001000000011000000101000000000001010000010001000000000111000000001000000000001101000001000000000000000101110
011100010000000000000101011000000000000000110000101000000000000100010010100000000000010100000011000000000010000100001100000000001001000000011000000100100001000000100000001000010000001100000000100000010000110000000010000100000001100000011000000000000110000001000000010000011000000100000100010001000000101000000110000000000011100001000000000000000100011001000000000000010000010101000000000011000001010000000000001100000101000000000000110001010
011100010000000000000101011000000000000000110000110000000000000100010001100000000000010100000110000000000010000100011000000000001001000001100000000101000001000100000000000100010000011000000000110000000001100000000011000000000110000000001100000000011000000000110000010001000000000001000100001100000000001100000000110000000000110000010010000000000011000100001000000000001110000001000000000000011000011000000000000001100101000000000000000011110
010110001000000000000101011000000000000000010101100000000000000101000011000000000000110000000110000000000011000000011000000000001000010001100000000000100100000011000000100100000100001000000000010001010000100000000011000100000010000000001100000000011000000000100000010001100000000010000100000110000000011000000100010000000000100001010001000000000011000100001000000000001100000101000000000000110001010000000000000011000101000000000000000111010
011100010000000000000101011000000000000000110000101000000000000100010010100000000000010100000110000000000010000100011000000000001001000000110000000100100001000001000000001000010000011000000000110000000001100000000011000000000110000000001000000100011000000000100001000001100000000101000000000110000000011100000000010000000000110000000011000000000011000001001000000000001100010100000000000000110001001000000000000011100001000000000000000110110
011100010000000000000101011000000000000000110000101000000000000100010000110000000000010101000001000000000010010100000100000000001001000000011000000100000001100000100000001000010000001100000000100010000000011000000100000001000001100000010000010100000100000001000001010000100000000100000101000010000000101000010000001000000011000000010001000000000100000101001000000000110000010010000000000011100000010000000000000010001101000000000000001110010
011100010000000000000101011000000000000000110000101000000000000100010000110000000000010100000011000000000010000100001100000000001001001000010000000100000001100001000000001000110000000100000000100010000001010000000110000000000011000000011000000100001000000001000001010000100000000100000100100010000000010100000100001000000001000011000010000000000110000001001000000000011000010100000000000000100001011000000000000010100101000000000000001010110
011100100000000000000101011000000000000000110001010000000000000100010001100000000000010100000011000000000011000000001100000000100000011000010000000001000100000110000000000100100000001100000000100000010000110000000010000100000011000000011000000000001100000001010000000000110000000110000001000010000000001000010000011000000001100000010001000000000110000101000000000000011000010001000000000001100000011000000000000111000100000000000000001101100
010110000100000000000101001100000000000000010100011000000000000101000001010000000000100001000001100000000010010000000110000000010000010000011000000001000100000000110000001100000010000010000100000000011000001000000100001100000000100000010000100000001010000011000000010000010000001100000101000000000000100000010100010000000010000001010001000000011000000100100000000000101000000101000000000010000011001000000000001101000001000000000000000101110
011100100000000000000101110000000000000000110001010000000000000110000001100000000000010001000110000000000001010000011000000000100000011000100000000001000100001010000000000100100000101000000000110000000001100000000011000000000110000000001010000010010000000000101000010001000000000010001100000100000000001100000001010000000000110000000011000000000011000000101000000000000101000110000000000000010011001000000000000001101001000000000000000110110
010110000100000000000101001100000000000000010100011000000000000101000001010000000000100001000101000000000010010100000100000000010001010000010000000001000100000001100000001100000010000100000100010000010000010000000100001100000001000000010000000100010100000001000001010000100000000100000101000100000000010000010000011000000011000000001001000000000101000001010000000000010000110001000000000001110000010000000000000001010101000000000000001101010
010110001000000000000101001100000000000000010100110000000000000101000010100000000000100001000011000000000010010000000110000000011000000000011000000001100000000001100000100000000110000010000000100001000000101000000010001001000010000000010000010100000100000001000001010000010000001100000100000010000000110000000000011000000010100000001001000000001010000001100000000000100000110001000000000001000010011000000000000111000100000000000000001101100
010110000100000000000101011000000000000000010100110000000000000101000001100000000000110000000011000000000010000100001100000000001001000000011000000001000001000001100000000100010000000011000100100000010000001000000010000100000001100000011000000000000110000001000000010000011000000100000101000001000000110000010000001000000010000000010011000000001000000100110000000001110000000100000000000011000011000000000000001100110000000000000000111100000
011100010000000000000101011000000000000000110000101000000000000100010010100000000000010100000011000000000010000100001100000000001001000000011000000100100001000000100000001000010000001010000000100000010000101000000010000101000000100000011000010000000100000001000000010001100000000100000100000011000000101000000010001000000010100000010010000000001000001100001000000000100100000110000000000011100001000000000000000010101001000000000000011010010
Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ 23 if the 3-connected ones are all you need. Perhaps more if you allow lower connectivity or multiple edges. $\endgroup$
    – Brendan McKay
    Commented Dec 18, 2023 at 10:50
  • 1
    $\begingroup$ Actually if such a graph exists then it shall be 4-edge-connected by a known result. I used plantri but it takes a couple of hours. Maybe I had some thing wrong while using plantri. I just commanded plantri 23 -p -m4 -e46 -f4 . So what is the correct command for the program? If possible, can you return me the output graphs here, either in -a or -T form. Thanks. $\endgroup$
    – Xin Zhang
    Commented Dec 19, 2023 at 3:05
  • 1
    $\begingroup$ @XinZhang If the theory says that the graph is 4-edge-connected and simple (no multiple edges), or you don't want multiple edges, the quickest command is plantri -q -g -c2 23 which makes the duals. Filter through pickg as Gordon says. Or you can get the duals directly with "plantri -q -g -c2 -d 23 | pickg -T8". If you get serious about larger sizes, the optimal path is to add a filter inside plantri to remove the graphs with the wrong degrees. There are hooks for such purpose but they aren't so easy to use. $\endgroup$
    – Brendan McKay
    Commented Dec 20, 2023 at 12:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .