On independent domination in direct products

DOI10.1007/S00373-022-02600-0MaRDI QIDQ2680574zbMATH OpenOpenAlexFDO

Authors Kirsti Kuenzel, Douglas F. Rall

Publication date 4 January 2023

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.12397

zbMATH Keywords

direct productindependent domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Abstract: In cite{nr-1996} Nowakowski and Rall listed a series of conjectures involving several different graph products. In particular, they conjectured that $i(GimesH)gei(G)i(H)$ where $i(G)$ is the independent domination number of $G$ and $GimesH$ is the direct product of graphs $G$ and $H$. We show this conjecture is false, and, in fact, construct pairs of graphs for which $mini(G),i(H)-i(GimesH)$ is arbitrarily large. We also give the exact value of $i(Gimes{K}_n)$ when $G$ is either a path or a cycle.

Recommendations

• On the existence and uniqueness of a solution of a nonlinear integral equation
• Stability in variation for nonlinear integro-differential equations
• scientific article; zbMATH DE number 4200908
• On solvability of a class of nonlinear second order integro-differential equations in the space \(W_1^2(\mathbb{R}^+)\)
• Nontrivial solvability of a class of nonlinear integro-differential equations of second order

Cites work

• Associative graph products and their independence, domination and coloring numbers
• Dominating direct products of graphs
• scientific article; zbMATH DE number 68351 (Why is no real title available?)
• scientific article; zbMATH DE number 1109407 (Why is no real title available?)
• scientific article; zbMATH DE number 2192179 (Why is no real title available?)
• Independence in direct-product graphs
• Independence numbers of product graphs
• Independence ratios of graph powers
• Independent domination in graphs: A survey and recent results
• Independent sets in tensor graph powers
• On domination and independent domination numbers of a graph
• On idomatic partitions of direct products of complete graphs
• On the ultimate categorical independence ratio
• On well-covered direct products
• The independence number of the Cartesian product of graphs.
• The Ultimate Categorical Independence Ratio of a Graph
• Vizing-like conjecture for the upper domination of Cartesian products of graphs -- the proof

Cited in

(7)

• Fractional domination of strong direct products
• Isoperimetry, stability, and irredundance in direct products
• On stability of non-domination under taking products
• On idomatic partitions of direct products of complete graphs
• On the independent semitotal domination in lexicographic product graphs
• Fine-grained complexity of multiple domination and dominating patterns in sparse graphs
• Fine-grained classification of detecting dominating patterns

This page was built for publication: On independent domination in direct products

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