Generalizating path and fan graphs: subcoloring and toughness

AUTOR(ES)

Markenzon, Lilian, Waga, Christina F.E.M.

FONTE

Pesqui. Oper.

DATA DE PUBLICAÇÃO

08/04/2014

RESUMO

Two graph classes are presented; the first one (k-ribbon) generalizes the path graph and the second one (k-fan) generalizes the fan graph. We prove that they are subclasses of chordal graphs and so they share the same structural properties of this class. The solution of two problems are presented: the determination of the subchromatic number and the determination of the toughness. It is shown that the elements of the new classes establish bounds for the toughness of k-path graphs.

Documentos Relacionados

• SHORTEST PATHS ON DYNAMIC GRAPHS: A SURVEY
• Description of continuous data using bar graphs: a misleading approach
• The public good game on graphs: can the pro-social behavior persist?
• Insights into the quaternary association of proteins through structure graphs: a case study of lectins
• Two novel genes, fanA and fanB, involved in the biogenesis of K99 fimbriae.