On total isolation in graphs

Geoffrey Boyer; Wayne Goddard; Michael A. Henning

doi:10.1007/s00010-024-01057-1

On total isolation in graphs

Geoffrey Boyer, Wayne Goddard, Michael A. Henning

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

An isolating set in a graph is a set S of vertices such that removing S and its neighborhood leaves no edge; it is total isolating if S induces a subgraph with no vertex of degree 0. We show that most graphs have a partition into two disjoint total isolating sets and characterize the exceptions. Using this we show that apart from the 7-cycle, every connected graph of order n≥4 has a total isolating set of size at most n/2, which is best possible.

Original language	English
Pages (from-to)	623-633
Number of pages	11
Journal	Aequationes Mathematicae
Volume	99
Issue number	2
DOIs	https://doi.org/10.1007/s00010-024-01057-1
Publication status	Published - Apr 2025

ASJC Scopus subject areas

General Mathematics
Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1007/s00010-024-01057-1

Cite this

@article{330ebe09a49342ab9d1d94bad06cc35a,

title = "On total isolation in graphs",

abstract = "An isolating set in a graph is a set S of vertices such that removing S and its neighborhood leaves no edge; it is total isolating if S induces a subgraph with no vertex of degree 0. We show that most graphs have a partition into two disjoint total isolating sets and characterize the exceptions. Using this we show that apart from the 7-cycle, every connected graph of order n≥4 has a total isolating set of size at most n/2, which is best possible.",

author = "Geoffrey Boyer and Wayne Goddard and Henning, {Michael A.}",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive licence to Springer Nature Switzerland AG 2024.",

year = "2025",

month = apr,

doi = "10.1007/s00010-024-01057-1",

language = "English",

volume = "99",

pages = "623--633",

journal = "Aequationes Mathematicae",

issn = "0001-9054",

publisher = "Birkhauser Verlag Basel",

number = "2",

}

TY - JOUR

T1 - On total isolation in graphs

AU - Boyer, Geoffrey

AU - Goddard, Wayne

AU - Henning, Michael A.

PY - 2025/4

Y1 - 2025/4

N2 - An isolating set in a graph is a set S of vertices such that removing S and its neighborhood leaves no edge; it is total isolating if S induces a subgraph with no vertex of degree 0. We show that most graphs have a partition into two disjoint total isolating sets and characterize the exceptions. Using this we show that apart from the 7-cycle, every connected graph of order n≥4 has a total isolating set of size at most n/2, which is best possible.

AB - An isolating set in a graph is a set S of vertices such that removing S and its neighborhood leaves no edge; it is total isolating if S induces a subgraph with no vertex of degree 0. We show that most graphs have a partition into two disjoint total isolating sets and characterize the exceptions. Using this we show that apart from the 7-cycle, every connected graph of order n≥4 has a total isolating set of size at most n/2, which is best possible.

UR - http://www.scopus.com/inward/record.url?scp=105003769080&partnerID=8YFLogxK

U2 - 10.1007/s00010-024-01057-1

DO - 10.1007/s00010-024-01057-1

M3 - Article

AN - SCOPUS:105003769080

SN - 0001-9054

VL - 99

SP - 623

EP - 633

JO - Aequationes Mathematicae

JF - Aequationes Mathematicae

IS - 2

ER -

On total isolation in graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this