ﻻ يوجد ملخص باللغة العربية
Let $F$ be a connected graph with $ell$ vertices. The existence of a subgraph isomorphic to $F$ can be defined in first-order logic with quantifier depth no better than $ell$, simply because no first-order formula of smaller quantifier depth can distinguish between the complete graphs $K_ell$ and $K_{ell-1}$. We show that, for some $F$, the existence of an $F$ subgraph in emph{sufficiently large} connected graphs is definable with quantifier depth $ell-3$. On the other hand, this is never possible with quantifier depth better than $ell/2$. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some $F$ be arbitrarily small comparing to $ell$ but never smaller than the treewidth of $F$. Moreover, the definitions over highly connected graphs require quantifier depth strictly more than the density of $F$. Finally, we determine the exact values of these descriptive complexity parameters for all connected pattern graphs $F$ on 4 vertices.
Let $v(F)$ denote the number of vertices in a fixed connected pattern graph $F$. We show an infinite family of patterns $F$ such that the existence of a subgraph isomorphic to $F$ is expressible by a first-order sentence of quantifier depth $frac23,v
Given a graph $F$, let $I(F)$ be the class of graphs containing $F$ as an induced subgraph. Let $W[F]$ denote the minimum $k$ such that $I(F)$ is definable in $k$-variable first-order logic. The recognition problem of $I(F)$, known as Induced Subgrap
We investigate the power of graph isomorphism algorithms based on algebraic reasoning techniques like Grobner basis computation. The idea of these algorithms is to encode two graphs into a system of equations that are satisfiable if and only if if th
In the Maximum Common Induced Subgraph problem (henceforth MCIS), given two graphs $G_1$ and $G_2$, one looks for a graph with the maximum number of vertices being both an induced subgraph of $G_1$ and $G_2$. MCIS is among the most studied classical
In recent years, we have seen several approaches to the graph isomorphism problem based on generic mathematical programming or algebraic (Grobner basis) techniques. For most of these, lower bounds have been established. In fact, it has been shown tha