vértice de soporte

En teoría de grafos , un vértice de soporte es un vértice adyacente a una hoja (un vértice de grado uno). Los vértices de soporte desempeñan un papel importante en el estudio de la dominación en grafos, ya que todo vértice de soporte debe pertenecer a todo conjunto dominante mínimo. ^{[ 1 ]}

Dejar${\displaystyle G=(V,E)}$ser un grafo. Un vértice${\displaystyle v\in V}$se denomina vértice de soporte si${\displaystyle v}$es adyacente al menos a una hoja de${\displaystyle G}$. ^{[ 1 ]}

Un vértice de soporte se denomina vértice de soporte débil si es adyacente a exactamente una hoja, y vértice de soporte fuerte si es adyacente a dos o más hojas. ^{[ 2 ]}

• Cada vértice de soporte pertenece a cada conjunto dominante mínimo de un grafo. ^{[ 1 ]}
• Si un grafo no tiene ningún vértice de soporte débil, entonces su número de dominación es igual a su número de dominación certificado . ^{[ 3 ]}
• Cada vértice de soporte pertenece a cada conjunto dominante certificado mínimo de un grafo. ^{[ 3 ]}
• Un árbol${\displaystyle T}$del orden${\displaystyle n}$tiene una combinación perfecta si y solo si${\displaystyle \gamma _{t}^{\text{gr}}(T)=n}$, dónde${\displaystyle \gamma _{t}^{\text{gr}}}$denota el número de dominación total de Grundy. La caracterización de los árboles que alcanzan el límite inferior para este parámetro implica la estructura de los vértices de soporte: entre los árboles sin vértice de soporte fuerte, el límite${\displaystyle \gamma _{t}^{\text{gr}}(T)\geq {\tfrac {2}{3}}(n+1)}$sostiene. ^{[ 4 ]}

• Hoja (teoría de grafos)
• Conjunto dominante