Inductive kernels of graphs

MaRDI QIDQ4583876zbMATH OpenFDO

Authors Serge Burckel

Publication date 3 September 2018

Full work available at URL https://arxiv.org/abs/0710.1551, http://www.oldcitypublishing.com/journals/mvlsc-home/mvlsc-issue-contents/mvlsc-volume-27-number-2-3-2016/mvlsc-27-2-3-p-175-181/

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: It is well known that kernels in graphs are powerful and useful structures, for instance in the theory of games. However, a kernel does not always exist and Chv'atal proved in 1973 that it is an NP-Complete problem to decide its existence. We present here an alternative definition of kernels that uses an inductive machinery : the inductive kernels. We prove that inductive kernels always exist and a particular one can be constructed in quadratic time. However, it is an NP-Complete problem to decide the existence of an inductive kernel including (resp. excluding) some fixed vertex.

Recommendations

• Combinatorial game theory foundations applied to digraph kernels
• scientific article; zbMATH DE number 6194066
• On the existence and the number of (2-d)-kernels in graphs.
• Strong kernel in certain oriented networks
• Kernel in Oriented Circulant Graphs

Cited in

(1)

• The journey of graph kernels through two decades

This page was built for publication: Inductive kernels of graphs

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