Bipartization of graphs

Mateusz Miotk , Jerzy Topp , Paweł Żyliński

Abstract

A dominating set of a graph G is a set D⊆VG such that every vertex in VG−D is adjacent to at least one vertex in D, and the domination number γ(G) of G is the minimum cardinality of a dominating set of G. In this paper we provide a new characterization of bipartite graphs whose domination number is equal to the cardinality of its smaller partite set. Our characterization is based upon a new graph operation.
Author Mateusz Miotk (FMPI / II)
Mateusz Miotk,,
- Institute of Informatics
, Jerzy Topp (FMPI / II)
Jerzy Topp,,
- Institute of Informatics
, Paweł Żyliński (FMPI / II)
Paweł Żyliński,,
- Institute of Informatics
Journal seriesGraphs and Combinatorics, ISSN 0911-0119, (N/A 70 pkt)
Issue year2019
Vol35
No5
Pages1169-1177
Publication size in sheets0.5
Keywords in Englishbipartite graph, bipartization, domination number
ASJC Classification2607 Discrete Mathematics and Combinatorics; 2614 Theoretical Computer Science
DOIDOI:10.1007/s00373-019-02068-5
URL https://link.springer.com/content/pdf/10.1007%2Fs00373-019-02068-5.pdf
Languageen angielski
LicenseOther; published final; Uznanie Autorstwa (CC-BY); with publication
Score (nominal)70
ScoreMinisterial score = 70.0, 30-09-2019, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2017 = 1.002; WoS Impact Factor: 2017 = 0.481 (2) - 2017=0.599 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back