The Inductive Kernels of Graphs

Simple item page
dc.creatorBurckel, Serge
dc.date2007-10-08
dc.date.accessioned2026-07-07T08:34:45Z
dc.date.available2026-07-07T08:34:45Z
dc.descriptionIt 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átal 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.
dc.description6 pages, 6 figures
dc.identifierhttps://arxiv.org/abs/0710.1551
dc.identifierhttp://arxiv.org/abs/0710.1551
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/139546
dc.subjectCombinatorics
dc.subjectOptimization and Control
dc.titleThe Inductive Kernels of Graphs
dc.typetext

Files

Collections

arXiv