Triangle strings: Structures for augmentation of vertex-disjoint triangle sets

Zan-Bo Zhang, X. Zhang

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Vertex-disjoint triangle sets (triangle sets for short) have been studied extensively. Many theoretical and computational results have been obtained. While the maximum triangle set problem can be viewed as the generalization of the maximum matching problem, there seems to be no parallel result to Berge's augmenting path characterization on maximum matching (C. Berge, 1957 [1]). In this paper, we describe a class of structures called triangle string, which turns out to be equivalent to the class of union of two triangle sets in a graph. Based on the concept of triangle string, a sufficient and necessary condition that a triangle set can be augmented is given. Furthermore, we provide an algorithm to determine whether a graph G with maximum degree 4 is a triangle string, and if G is a triangle string, we compute a maximum triangle set of it. Finally, we give a sufficient and necessary condition for a triangle string to have a triangle factor
Original languageEnglish
Pages (from-to)450-456
JournalInformation processing letters
Volume114
Issue number8
DOIs
Publication statusPublished - 2014

Keywords

  • METIS-311113
  • IR-96681

Fingerprint Dive into the research topics of 'Triangle strings: Structures for augmentation of vertex-disjoint triangle sets'. Together they form a unique fingerprint.

Cite this