kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Exploring the influence of graph operations on zero forcing sets
KTH, School of Electrical Engineering and Computer Science (EECS), Human Centered Technology, Media Technology and Interaction Design, MID.ORCID iD: 0000-0002-6711-0584
Department of Mathematics, Indian Institute of Technology (IIT) Bhilai, India.
2025 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 348, no 8, article id 114516Article in journal (Refereed) Published
Abstract [en]

Zero forcing in graphs is a coloring process where a vertex colored blue can force its unique uncolored neighbor to be colored blue. A zero forcing set is a set of initially blue vertices capable of eventually coloring all vertices of the graph. In this paper, we focus on the numbers z(G;i), which is the number of zero forcing sets of size i of the graph G. These numbers were initially studied by Boyer et al. [5] where they conjectured that for any graph G on n vertices, z(G;i)≤z(Pn;i) for all i≥1 where Pn is the path graph on n vertices. The main aim of this paper is to show that several classes of graphs, including outerplanar graphs and threshold graphs, satisfy this conjecture. We do this by studying various graph operations and examining how they affect the number of zero forcing sets.

Place, publisher, year, edition, pages
Elsevier BV , 2025. Vol. 348, no 8, article id 114516
Keywords [en]
Outerplanar graph, Path graph, Threshold graph, Tree, Zero forcing set
National Category
Discrete Mathematics Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-362521DOI: 10.1016/j.disc.2025.114516ISI: 001464476700001Scopus ID: 2-s2.0-105001828255OAI: oai:DiVA.org:kth-362521DiVA, id: diva2:1952969
Note

QC 20250422

Available from: 2025-04-16 Created: 2025-04-16 Last updated: 2025-04-22Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Menon, Arjun Rajendran

Search in DiVA

By author/editor
Menon, Arjun Rajendran
By organisation
Media Technology and Interaction Design, MID
In the same journal
Discrete Mathematics
Discrete MathematicsComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 10 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf