1
$\begingroup$

The definition of Graph Diagonals, that are the subject of this question, is based on the notions of crossing edges and on connected graphs:

Two edges $AC$ and $BD$ of a complete, symmetric and weighted graph are said to be crossing (each other) iff

    $A$, $B$, $C$ and, $D$ are distinct vertices and
    $AC+BD > AB+CD$ and $AC+BD > AD+BC$

An edge $AB$ of a complete, symmetric and weighted graph,is then defined to be a diagonal of the graph iff

    removing from the graph all edges that are crossing edge $AB$ and
    removing vertices $A$ and $B$

disconnects the graph

One important property of those graph diagonals is that they can't appear in an optimal tour through all vertices of the graph.

From some experiments I observed that at least every 6th edge was such a diagonal and with increasing number of vertices almost all vertices were adjacent to such a diagonal.

My question is, whether the lower bound of $n(n+1)/12$ diagonals can be confirmed.

$\endgroup$
3
  • $\begingroup$ Can you clarify what you mean by a "symmetric" complete graph? $\endgroup$
    – Casteels
    Mar 9, 2013 at 22:28
  • $\begingroup$ "symmetric" means that the edges are undirected (I had the symmetric TSP in mind, but I agree that I should have been more precise here). A complete graph is one where every pair of vertices corresponds to an edge with an associated weight. $\endgroup$ Mar 10, 2013 at 6:16
  • $\begingroup$ Oh ok, thanks. Next question: Does AC mean the weight of the edge from vertex A to vertex C? If so, then setting all weights to 1 gives zero diagonals... $\endgroup$
    – Casteels
    Mar 10, 2013 at 20:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.