abc-graphs

A connected graph is independent edge failure immune if no matching (a set of edges without common end-vertices) disconnects it. It is edge minimal if it has the minimum number of edges among all graphs with a given number n of vertices having this property. This minimum number of edges is m=\lceil 3(n-1)/2 \rceil and achieved by the so called abc-graphs, i.e., the graphs that can be obtained from a C_3 by a finite number of applications of two operations:
append a C_3 sharing a vertex with the existing graph;
replace an edge by a C_4 for which the edge would be a diagonal
and of at most one operation of
adding a vertex adjacent to any two vertices of a graph with odd number of vertices,
cf. A.M.Farley and A. Proskurowski, Extremal graphs with no disconnecting matching, Proceedings of the 14th South-Eastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, Congressus Numerantium 41 (1984), 153-165 (see also A.M.Farley and A. Proskurowski, Networks immune to isolated line failures, Networks 12, 4(1982), 393-403).

Problem: Are the abc-graphs exactly the edge minimal independent edge failure immune graphs?

Back to the Problem Session page and to the workshop page