Structural and algorithmic studies on some graph modifications based on complementation

dc.contributor.guideR.B. Sandeep
dc.coverage.spatial
dc.creator.researcherPal, Sagartanu
dc.date.accessioned2025-12-03T09:20:10Z
dc.date.available2025-12-03T09:20:10Z
dc.date.awarded2025
dc.date.completed2025
dc.date.registered2018
dc.description.abstractComplementation is a very fundamental graph operation. The atomic operation in complemen- tation is to flip the adjacency between a pair of vertices, i.e., to add an edge between them if it does not exist, and to delete the edge if it exists. We conduct structural and algorithmic study of three kinds of graph complementations, namely, subgraph complementation, switching, and local complementation. Each of these complementations is specified by a pair (G, S), where G is a graph and S is a subset of its vertices. In subgraph complementation, the subgraph induced by S is complemented. In switching, the adjacencies of pairs u, v of vertices are flipped, where u is from S and v is from V (G) \ S. Local complementation is a special type of subgraph complementation in which S is the set of neighbors of a vertex in G. newlineLet G be a graph class. Subgraph complementation to G is the problem defined as follows: for a given graph G, does there exist a subset S of vertices of G such that complementing the graph induced by S in G results in a graph in G? A comprehensive study of this problem was initiated by Fomin et al. (Algorithmica, 2020). We study the complexity of the problem when G is one of the following graph classes: Kt-free , paw-free, graphs with minimum degree at least r (a constant), {star, diamond}-free. We obtain polynomial-time algorithm in each case. Moreover, we show that Subgraph complementation to G is polynomially equivalent to Subgraph complementation to G, where G is the set of complements of graphs in G. Our results resolve two open problems, and subsume two main results by Fomin et al. (Algorithmica, 2020). newlineSwitching was introduced by van Lint and Seidel in 1966. Various aspects of switching have been studied for the last six decades. For a hereditary graph class G, there is a unique maximal subclass of G closed under switching, and a unique minimal superclass of G closed under switching. We refer to them as the maximum subclass of G closed under switching and the minimum superclass of G closed under s
dc.description.note
dc.format.accompanyingmaterialDVD
dc.format.dimensions30 cm
dc.format.extentxv, 97 p.
dc.identifier.researcherid0009-0009-2071-1292
dc.identifier.urihttp://hdl.handle.net/10603/677807
dc.languageEnglish
dc.publisher.institutionDepartment of Computer Science and Engineering
dc.publisher.placeDharwad
dc.publisher.universityIndian Institute of Technology Dharwad
dc.relation
dc.rightsuniversity
dc.source.universityUniversity
dc.subject.keywordHereditary graph class
dc.subject.keywordLocal complementation
dc.subject.keywordPolynomial-time algorithm
dc.subject.keywordSubgraph complementation
dc.subject.keywordSwitching
dc.titleStructural and algorithmic studies on some graph modifications based on complementation
dc.title.alternative
dc.type.degreePh.D.

Files

Original bundle

Now showing 1 - 5 of 14
Loading...
Thumbnail Image
Name:
01_title.pdf
Size:
267.92 KB
Format:
Adobe Portable Document Format
Description:
Attached File
Loading...
Thumbnail Image
Name:
02_prelim pages.pdf
Size:
346.71 KB
Format:
Adobe Portable Document Format
Loading...
Thumbnail Image
Name:
03_contents.pdf
Size:
101.87 KB
Format:
Adobe Portable Document Format
Loading...
Thumbnail Image
Name:
04_abstract.pdf
Size:
115.93 KB
Format:
Adobe Portable Document Format
Loading...
Thumbnail Image
Name:
05_chapter1.pdf
Size:
158.05 KB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.79 KB
Format:
Plain Text
Description: