On the P₃-hull number of Kneser graphs

DOI10.37236/9903MaRDI QIDQ2048567zbMATH OpenOpenAlexFDO

Authors Luciano N. Grippo, Adrián Pastine, P. Torres, Mario Valencia-Pabon, Juan Vera

Publication date 9 August 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/9903

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

infection spreading in a graphKneser graph

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85) Other problems of combinatorial convexity (52A37)

Review text

Summary: This paper considers an infection spreading in a graph; a vertex gets infected if at least two of its neighbors are infected. The \(P_3\)-hull number is the minimum size of a vertex set that eventually infects the whole graph. In the specific case of the Kneser graph \(K(n,k)\), with \(n\geqslant 2k+1\), an infection spreading on the family of \(k\)-sets of an \(n\)-set is considered. A set is infected whenever two sets disjoint from it are infected. We compute the exact value of the \(P_3\)-hull number of \(K(n,k)\) for \(n>2k+1\). For \(n = 2k+1\), using graph homomorphisms from the Knesser graph to the Hypercube, we give lower and upper bounds.

Recommendations

• On the \(P_3\)-hull numbers of \(q\)-Kneser graphs and Grassmann graphs
• On the P₃-hull number of Hamming graphs
• Geodetic convexity and Kneser graphs
• Infection in hypergraphs
• On the \(P_3\)-hull number of some products of graphs

Cites work

• An upper bound on the \(P_3\)-Radon number
• Complexity results related to monophonic convexity
• Convex partitions of graphs induced by paths of order three
• Convex sets in graphs. II: Minimal path convexity
• Convexities related to path properties on graphs
• Explicit 2-factorizations of the odd graph
• Geodesic Convexity in Graphs
• Geodetic number versus hull number in P₃-convexity
• Graphs with intrinsic s3 convexities
• Grundy domination and zero forcing in Kneser graphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 4050423 (Why is no real title available?)
• scientific article; zbMATH DE number 5066400 (Why is no real title available?)
• Inapproximability results for graph convexity parameters
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Kneser's conjecture, chromatic number, and homotopy
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Minimal percolating sets in bootstrap percolation
• On slowly percolating sets of minimal size in bootstrap percolation
• On the P₃-hull number of Hamming graphs
• On the approximability of influence in social networks
• On the Carathéodory number for the convexity of paths of order three
• On the diameter of Kneser graphs
• Some Elementary Properties of Interval Convexities
• The maximum time of 2-neighbor bootstrap percolation: complexity results
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects

Cited in

(8)

• On the \(P_3\)-hull number of some products of graphs
• On the \(P_3\)-hull numbers of \(q\)-Kneser graphs and Grassmann graphs
• Geodetic convexity and Kneser graphs
• Bootstrap percolation in strong products of graphs
• Minimum 2-percolating sets in 2-connected, diameter 2 graphs
• Bootstrap percolation and P₃-hull number in direct products of graphs
• 3-neighbor bootstrap percolation on grids
• Monophonic number of Kneser graphs and strongly 2-monophonic graphs

This page was built for publication: On the \(P_3\)-hull number of Kneser graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2048567)