DSpace-CRIS UAEMEXhttp://ri.uaemex.mx/crisThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Tue, 19 Jan 2021 19:40:29 GMT2021-01-19T19:40:29Z5011Computing the Clique-width of Cactus Graphshttp://ri.uaemex.mx/handle20.500.11799/67667Title: Computing the Clique-width of Cactus Graphs
Authors: JOSE RAYMUNDO MARCIAL ROMERO; JOSE ANTONIO HERNANDEZ SERVIN; JACOBO LEONARDO GONZALEZ RUIZ
Description: Similar to the tree-width (twd), the clique-width (cwd) is an invariant of graphs. A well known relationship between tree-width and clique-width is that cwd(G) ≤ 3 · 2twd(G)−1. It is also known that tree-width of Cactus graphs is 2, therefore the clique-width for those graphs is smaller or equal than 6. In this paper, it is shown that the clique-width of Cactus graphs is smaller or equal to 4 and we present a polynomial time algorithm which computes exactly a 4-expression.
http://ri.uaemex.mx/handle20.500.11799/67667