Wyniki wyszukiwania - Biblioteka Nauki

Ten serwis zostanie wyłączony 2025-02-11.

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: mathematics - combinatorics

Sortuj według:

Ogranicz wyniki do:

Elimination distance to bounded degree on planar graphs

100%

Lindermayr A. , Siebertz S. , Vigny A.

Fundamenta Informaticae

2024

tom Vol. 191, nr 2

129--140

We study the graph parameter elimination distance to bounded degree, which was introduced by Bulian and Dawar in their study of the parameterized complexity of the graph isomorphism problem. We prove that the problem is ﬁxed-parameter tractable on planar graphs, that is, there exists an algorithm that given a planar graph G and integers d, k decides in time f(k, d) · nc for a computable function f and constant c whether the elimination distance of G to the class of degree d graphs is at most k.

On the Tutte and matching polynomials for complete graphs

88%

Kotek T. , Makowsky J. A.

Fundamenta Informaticae

2022

tom Vol. 186, nr 1-4

155--173

Let T(G; X, Y) be the Tutte polynomial for graphs. We study the sequence ta,b(n) = T(Kn; a, b) where a, b are integers, and show that for every μ ∈ ℕ the sequence ta,b(n) is ultimately periodic modulo μ provided a ≠ 1 mod μ and b ≠ 1 mod μ. This result is related to a conjecture by A. Mani and R. Stones from 2016. The theorem is a consequence of a more general theorem which holds for a wide class of graph polynomials definable in Monadic Second Order Logic. This gives also similar results for the various substitution instances of the bivariate matching polynomial and the trivariate edge elimination polynomial ξ(G; X, Y, Z) introduced by I. Averbouch, B. Godlin and the second author in 2008. All our results depend on the Specker-Blatter Theorem from 1981, which studies modular recurrence relations of combinatorial sequences which count the number of labeled graphs.