Search

In this paper, we define a class of auxiliary graphs associated with simple undirected graphs. This class of auxiliary graphs is based on the set of spanning trees of the original graph and the edges constituting those spanning trees. A class of auxiliary graphs can be viewed as a function from the class of graphs to the class of graphs. We provide mathematical characterisation of graphs which are the spanning tree auxiliary graphs of some simple graph. Since the class of spanning tree auxiliary graphs of graphs do not have unique preimages (the forward function is not injective), we derive precisely the classes of graphs which have the same auxiliary graph. We design algorithms for computing a basic preimage and define rules to get other solutions for the same auxiliary graph. We also obtain several results expressing parameters of the auxiliary graph in terms of (not necessarily the same) parameters of the original graph.

Graphs constructed to translate some graph problem into another graph problem are usually called auxiliary graphs. Specifically total graphs of simple graphs are used to translate the total colouring problem of the original graph into a vertex colouring problem of the transformed graph. In this paper, we obtain a new characterisation of total graphs of simple graphs. We also design algorithms to compute the inverse total graphs when the input graph is a total graph. These results improve over the work of Behzad, by using novel observations on the properties of the local structure in the neighbourhood of each vertex. The earlier algorithm was based on bfs and distances. Our theorems result in partitioning the vertex set of the total graph into the original graph and the line graph efficiently. We obtain constructive results for special classes, most notably for total graph of complete graphs.

Given a set of nonempty subsets of some universal set, their intersection graph is defined as the graph with one vertex for each set and two vertices are adjacent precisely when their representing sets have non-empty intersection. Sometimes these sets are finite, but in many well known examples like geometric graphs (including interval graphs) they are infinite. One can also study the reverse problem of expressing the vertices of a given graph as distinct sets in such a way that adjacency coincides with intersection of the corresponding sets. The sets are usually required to conform to some template, depending on the problem, to be either a finite set, or some geometric set like intervals, circles, discs, cubes etc. The problem of representing a graph as an intersection graph of sets was first introduced by Erdos and they looked at minimising the underlying universal set necessary to represent any given graph. In that paper it was shown that the problem is NP complete. In this paper we study a natural variant of this problem which is to consider graphs where vertices represent distinct sets and adjacency coincides with disjointness. Although this is really the same problem on the complement graph, for specific families of graphs this is a more natural way of viewing it. When taken across the spectrum of all graphs the two problems are evidently identical. Our motivation to look at disjointness instead of intersection is that several well known graphs like the Petersen graph and Knesser graphs are expressed in the latter method, and the complements of these families are not well studied. The parameters we take into account are the maximum size of an individual vertex label, minimum universe size possible (disregarding individual label sizes) and versions of these two where it is required that each vertex gets labels of the same size.

The acyclic chromatic index, denoted by $a'(G)$, of a graph $G$ is the minimum number of colours used in any proper edge colouring of $G$ such that the union of any two colour classes does not contain a cycle, that is, forms a forest. We show that $a'(G\Box H)\le a'(G) + a'(H)$ for any two graphs $G$ and $H$ such that $max\{a'(G), a'(H)\} > 1$. Here, $G \Box H$ denotes the cartesian product of $G$ and $H$. This extends a recent result of [15] where tight and constructive bounds on $a'(G)$ were obtained for a class of grid-like graphs which can be expressed as the cartesian product of a number of paths and cycles.

The acyclic edge colouring problem is extensively studied in graph theory. The corner-stone of this field is a conjecture of Alon et. al.\cite{alonacyclic} that $a'(G)\le \Delta(G)+2$. In that and subsequent work, $a'(G)$ is typically bounded in terms of $\Delta(G)$. Motivated by this we introduce a term $gap(G)$ defined as $gap(G)=a'(G)-\Delta(G)$. Alon's conjecture can be rephrased as $gap(G)\le2$ for all graphs $G$. In \cite{manusccartprod} it was shown that $a'(G\Box H)\le a'(G)+a'(H)$, under some assumptions. Based on Alon's conjecture, we conjecture that $a'(G\Box H)\le a'(G)+\Delta(H)$ under the same assumptions, resulting in a strengthening. The results of \cite{alonacyclic} validate our conjecture for the class of graphs it considers. We prove our conjecture for a significant subclass of sub-cubic graphs and state some generic conditions under which our conjecture can be proved. We suggest how our technique can be potentially applied by future researchers to expand the class of graphs for which our conjecture holds. Our results improve the understanding of the relationship between Cartesian Product and acyclic chromatic index., Comment: 10 pages, 5 figures