FindDominationNumber

This repository contains a program created for the article "J. Renders, S. Tokunaga, C.T. Zamfirescu: Domination of Triangulated Discs and Maximal Outerplanar Graphs, manuscript".

The program uses McKay's graph6 format to read and write graphs. See http://users.cecs.anu.edu.au/~bdm/data/formats.txt. As well as Brinkmann and Mckay's planar code format. The definition can be found in the plantri manual. See https://users.cecs.anu.edu.au/~bdm/plantri/plantri-guide.txt.

Short manual

This program can be used to determine the domination number of a given input graph. One can also count the number of minimal dominating sets and output graphs with a specific domination number. Moreover, the program contains methods for filtering graphs which satisfy certain conditions involving disjoint paths. In particular, the conditions of Lemma 1, Lemma 2 and Lemma 3 of the manuscript can be checked.

This program supports graphs with less than 64 vertices.

Installation

This requires a working shell and make. Navigate to the folder containing findDominationNumber.c and compile using make to create a binary.

Use make clean to remove the binary created in this way.

Usage of findDominationNumber

All options can be found by executing ./findDominationNumber -h.

Usage: ./findDominationNumber [-2|-3|-k#] [-c] [-d] [-o#] [-v] [-h]

By default this program computes the domination number of the input graphs. With -o# graphs with domination number # are output. When using either of -2, -3 or -k# the graphs which satisfy the conditions of Lemma 1, 2 and 3, respectively are output.

Graphs are read from stdin in graph6 format by default or in planar code format if -d is present. Graphs are sent to stdout in graph6 format or planar code depending on the presence of -d. If the input graph had a header, so will the output graph.

The order in which the arguments appear does not matter. -2, --K2-lemma Check if the input graph satisfies the conditions of Lemma 1; with -d the input graphs are assumed to be triangulated discs; Otherwise behavior is unexpected; without -d there may be false positives -3, --P3-lemma Check if the input graph satisfies the conditions of Lemma 2; with -d the input graphs are assumed to be 3-connected triangulated discs; Otherwise behavior is unexpected; without -d there may be false positives -k#, --Pk-lemma=# Check if the input graph satisfies the conditions of Lemma 3 for connectivity #; requires -d and the input graphs as assumed to be triangulated discs; Otherwise behavior is unexpected -c, --count Count the number of minimal dominating sets; The min, max and avg of all input graphs will be output; cannot be used with -2, -3 or -k# -d, --triangulated-disc Read the input graphs in planar code; the boundary cycle will be computed; will lead to unexpected behavior if it is not a triangulated disc and -2, -3 or -k# is used -o#, --output=# Output graphs with domination number #; cannot be used with -2, -3 or -k# -v, --verbose Give more detailed output -h, --help Print this help text

Examples

./findDominationNumber Compute the domination number of the input graphs. One can see how many graphs have a specific domination number.

./findDominationNumber -c Compute the domination number of the input graphs and count the minimal dominating sets. The maximum, minimum and average number of minimal dominating sets of all input graphs is given.

./findDominationNumber -2 Compute the domination number of the input graphs and send to stdout if they satisfy the conditions of Lemma 1. Inputting the triangulated discs in planar code and using -d is faster as the boundary cycle is known in this case. Note that without using -d the algorithm looks at all copies of K2 in the graph, which may lead to false positive. These need to be manually inspected to figure out if the copy of K2 lies on the boundary cycle.

./findDominationNumber -2 -v Same as the previous example, but also prints out which copies of K2 satisfy the conditions.

./findDominationNumber -o# Compute the domination number of the input graphs and send those with domination number # to stdout.

Graphs in graph6 or planar code format can be sent to stdin via a file: ./findDominationNumber < location/of/file.g6 ./findDominationNumber -d < location/of/file.pl

Or directly via their graph6 code: ./findDominationNumber <<< 'IsP@OkWHG'

Or sent from the stdout of another program e.g. plantri, which outputs graphs in graph6 or planar code format: ./plantri | ./findDominationNumber -d

In the folder example/ we have added two files containing planar graphs, one in graph6 format and the other in planar code format, and the output of the program when using one of the files as input and using various command line arguments. Using 1> file.g6 sends the stdout of the program to a file named file.g6. We typically reserve this for graphs which are output by the program. 2>file.e sends the stderr of the program to a file named file.e. We typically reserve this for other information given by the program, such as number of graphs with certain domination numbers and runtime.

The file graphs_in_graph6_format.g6 contains six graphs in graph6 format: the octahedron, the graph from Figure 1 of the article, both graphs from Figure 2 of the article, the graph from Figure 3 of the article with k = 3 and the graph of Figure 4 of the article.

The file graphs_in_planar_code_format.pl contains these same graphs but in planar code format. Note that as this is a binary format it is difficult for a human to interpret these graphs. For more information on interpreting these graphs, see for example the explanation on https://houseofgraphs.org/help.

./findDominationNumber < example/graphs_in_graph6_format.g6 2> example/no_options_graph6.e This will compute the domination number for each of the 6 graphs and send it to stderr. No graphs will be output since we did not add any special flag.

./findDominationNumber -d < example/graphs_in_planar_code_format.pl 2> example/option_-d_planar_code.e This again will compute the domination number, but now we input the graphs as planar code. We need to add the flag -d to let the program know the input is planar code.

./findDominationNumber -o6 < example/graphs_in_graph6_format.g6 1> example/option_-o6_graph6.g6 2> example/option_-o6_graph6.e This computes the domination number and outputs all graphs with domination number 6. Output graphs are sent to stdout. In this example exactly one graph is written.

./findDominationNumber -c < example/graphs_in_graph6_format.g6 2> example/option_-c_graph6.e This will compute the domination number of the graphs, and also keep track of how many dominating sets attain this minimum. The minimum, maximum and average number of these dominating sets over all input graphs are given to stdout. No graphs are output.

./findDominationNumber -d -2 < example/graphs_in_planar_code_format.pl 1> example/option_-d_-2_planar_code.g6 2> example/option_-d_-2_planar_code.e Check the conditions of Lemma 1 for the input graphs and write the ones for which it holds to stdout. It is assumed graphs are 2-connected triangulated discs otherwise behaviour is unexpected. Except for the octahedron all graphs pass the conditions. It is recommended to use these options with graphs which are not triangulations in planar code format. Otherwise all copies of K_2 are tested and one needs to manually check whether they lie on the outer cycle.

./findDominationNumber -d -3 < example/graphs_in_planar_code_format.pl 1> example/option_-d_-3_planar_code.g6 2> example/option_-d_-3_planar_code.e Check the conditions of Lemma 2 for the input graphs and write the ones for which it holds to stdout. It is assumed graphs are 3-connected triangulated discs, otherwise behaviour is unexpected. This outputs both graphs from Figure 2 and the one from Figure 4.

./findDominationNumber -d -k4 < example/graphs_in_planar_code_format.pl 1> example/option_-d_-k4_planar_code.g6 2> example/option_-d_-k4_planar_code.e Check the conditions of Lemma 3 for the input graphs and write the ones for which it holds to stdout. It is assumed the graphs are triangulated discs. This time it is checked whether or not the graphs are 4-connected. This outputs only the graph from Figure 4.