On a characterization of graphs with perfect neighbourhood matrices

ESCALANTE, MARIANA SILVINA; HINRICHSEN, ERICA; LEONI, VALERIA

Buenos Aires

Conferencia; XXI Latin-Iberoamerican Conference on Operations Research; 2022

Universidad de Buenos Aires

The main purpose of this work is to study those graphs G with perfect neighbourhood matrix, N[G].This property implies the resolution of many optimization problems in polynomial time due to theintegrality of the polyhedron of feasible solutions of their linear relaxations. Given a 0-1 matrix M withn columns, Q(M) is the graph with n nodes and such that two nodes i and j are adjacent in Q(M) ifthere is a row in M with two ones in the corresponding positions. A 0-1 matrix is perfect if it is theclique-node matrix of Q(M) and Q(M) is a perfect graph. Due to the Perfect Graph Theorem, a graphis perfect if it has neither an odd hole nor an odd antihole as a node-induced subgraph. A square 0-1matrix is an extended clique node matrix of a graph G if every maximal clique in G has itscharacteristic vector as one of its rows and the remaining rows (if any) correspond to (non)-maximalcliques in G. First, in order to give a characterization of a graph with an extended clique nodeneighbourhood matrix, we define the set T of seven graphs, including the chordless cycles of lengthbetween 4 and 6, and the 3-sun, 1-pyramid, 2-pyramid and 3-pyramid graphs. We prove that N[G] isan extended clique node matrix if and only if every node-induced subgraph of G in the set T has acommon neighbour in G. We say that G' is a dominating subgraph of G in the node-set U if for everynode of G not in V(G'), there exists a node w in V(G') such that its neighbourhood N[v] is a subset ofN[w], restricted to the nodes in U. We found two families of graphs, called H-graphs and A-graphs.Using the previous definitions, we prove that Q(N[G]) does not have an induced odd hole if and onlyif G has no dominant H-graph, in an appropriate set of nodes of V(G). Finally, we show that Q(N[G])does not have an induced odd antihole if and only if G has neither an A-graph nor a web graph W^{t}_{4t+3} as dominant subgraphs, in an appropriate set of nodes of V(G).