|
 
|
[CPT10] On hypochordal graphs
Rapport Scientifique : Date de dépot: 2010/01/01, (Tech. Rep.: CEDRIC-10-1886)Mots clés: graph, tree, vertex-connected, N P-complete
Résumé:
We introduce graphs called hypochordal: for any path of length 2, there
exists a chord or another path of length 2 between its two endpoints. We
show that such graphs are 2-vertex-connected and moreover in the case of
an edge or a vertex deletion, the distance between any pair of nonadjacent
vertices remains unchanged.
We give properties of hypochordal graphs, then we study the class of
minimum hypochordal graphs and finally we give some complexity results
for classical combinatorial problems.
Keywords: graph, tree, vertex-connected, N P-complete
Commentaires:
Article soumis.
BibTeX
| @techreport { | |||
| CPT10, | |||
| title | = | "{On hypochordal graphs}", | |
| author | = | "M.-C. Costa and C. Picouleau and H. Topart", | |
| number | = | "{CEDRIC-10-1886}", | |
| institution | = | "{CEDRIC laboratory, CNAM-Paris, France}", | |
| date | = | {01-01-2010}, | |
| note | = | "{Article soumis.}", | |
| } | |||
