Contents

Ars Combinatoria

  • Research article

Proper Nearly Perfect Sets in Graphs

Ch. Eslabchi1, H.R. Maimani2,3, R. Torabi4, R. Tusserkani3
1Dept. of Math., Shahid Beheshti University, G.C. Tehran, Iran.
2Dept. of Math., Shahid Rajaee Teacher Training University, Tehran, Iran.
3School of Math., Institute for Research in Fundamental Sciences (IPM), Tehran, Iran.
4School of Math., Institute for Research in Fundamental Sciences (IPM), Tehran, fran.
  • Published: 30/04/2016

Abstract

In this paper, we present a new combinatorial problem, called the Nearly Perfect Bipartition Problem, which is motivated by a computer networks application. This leads to a new graph parameter, \(PN_p(G)\), which equals the maximum cardinality of a proper nearly perfect set. We show that the corresponding decision problem is \(NP\)-hard, even when restricted to graphs of diameter \(3\). We present several bounds for \(PN_p(G)\) and determine the value of \(PN_p(G)\) for several classes of graphs.

Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin

1970-2025 CP (Manitoba, Canada) unless otherwise stated.

Citation
Ch. Eslabchi, H.R. Maimani, R. Torabi, R. Tusserkani. Proper Nearly Perfect Sets in Graphs[J], Ars Combinatoria, Volume 126. 143-156. .