Relation to Median Graph and Whether a Graph Is Triangle-Free |

The problems of testing whether a graph is a mediangraph, and whether a graph is triangle-free, both had been well studied whenImrich, Klavžar & Mulder (1999) observed that, in some sense, they arecomputationally equivalent. Therefore, the best known time bound fortesting whether a graph is triangle-free, O(m1.41), applies as well to testing whether a graph isa median graph, and any improvement in median graph testing algorithms wouldalso lead to an improvement in algorithms for detecting triangles in graphs. In one direction, suppose one is given as input a graph G, and must test whether G is triangle-free. From G, construct a new graph H having as vertices each set ofzero, one, or two adjacent vertices of G. Two such sets are adjacent in Hwhen they differ by exactly one vertex. An equivalent description of H is that it is formed by splittingeach edge of G into a path oftwo edges, and adding a new vertex connected to all the original vertices of G. This graph H is by construction a partial cube,but it is a median graph only when Gis triangle-free: if a, b, and c form a triangle in G,then {a,b}, {a,c}, and {b,c} have nomedian in H, for such a medianwould have to correspond to the set {a,b,c}, but sets of three or more vertices of G do not form vertices in H. Therefore, G is triangle-free if and only if H is a median graph. In thecase that G is triangle-free, H is its simplex graph. Analgorithm to test efficiently whether His a median graph could by this construction also be used to test whether G is triangle-free. Thistransformation preserves the computational complexity of the problem, for thesize of H is proportional tothat of G. The reduction in the other direction, from triangledetection to median graph testing, is more involved and depends on the previousmedian graph recognition algorithm of Hagauer, Imrich & Klavžar (1999),which tests several necessary conditions for median graphs in near-lineartime. The key new step involves using a breadth first search to partitionthe graph into levels according to their distances from some arbitrarily chosenroot vertex, forming a graph in each level in which two vertices are adjacentif they share a common neighbor in the previous level, and searching fortriangles in these graphs. The median of any such triangle must be acommon neighbor of the three triangle vertices; if this common neighbor doesnot exist, the graph is not a median graph. If all triangles found inthis way have medians, and the previous algorithm finds that the graphsatisfies all the other conditions for being a median graph, then it mustactually be a median graph. Note that this algorithm requires, not justthe ability to test whether a triangle exists, but a list of all triangles inthe level graph. In arbitrary graphs, listing all triangles sometimesrequires Ω(m3/2)time, as some graphs have that many triangles, however Hagauer et al. show thatthe number of triangles arising in the level graphs of their reduction isnear-linear, allowing the Alon et al. fast matrix multiplication based techniquefor finding triangles to be used.