On some covering graphs of a graph - Shariefuddin Pirzada; Hilal A Ganie; Merajuddin Siddique (GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB, 2016)
For a graph G with vertex set V(G)={v_1, v_2, …, v_n}, let S be the covering set of G having the maximum degree over all the minimum covering sets of G. Let N_S[v]={uS : uv E(G) }{v} be the closed neighbourhood of the vertex v with respect to S. We define a square matrix A_S(G)= (a_ij), by a_ij=1, if |N_S[v_i]N_S[v_j] | ≥ 1, i≠ j and 0, otherwise. The graph G^S associated with the matrix A_S(G) is called the maximum degree minimum covering graph (MDMC-graph) of the graph G. In this paper, we give conditions for the graph G^S to be bipartite and Hamiltonian. Also we obtain a bound for the number of edges of the graph G^S in terms of the structure of G. Further we obtain an upper bound for covering number (independence number) of G^S in terms of the covering number (independence number) of G.