Abstract | ||
---|---|---|
Forward degree seqences, arising from orderings of the vertices in a graph, carry a lot of vital information about the graph. In this paper, we focus our work on two special classes of forward degree sequences, which we named balanced and strongly balanced. Our main result is to prove that any chordal graph has a strongly balanced forward degree sequence and any graph with all degrees at most 3 has a balanced forward degree sequence. Moreover, we show that the (strongly) balanced forward degree sequence can be computed in polynomial time in the above cases. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1007/11533719_69 | COCOON |
Keywords | Field | DocType |
special class,main result,forward degree seqences,forward degree sequence,balanced forward degree sequence,optimally balanced forward degree,polynomial time,vital information,chordal graph,degree sequence | Discrete mathematics,Combinatorics,Vertex (geometry),Loop (graph theory),Chordal graph,Quartic graph,Regular graph,Degree (graph theory),Frequency partition of a graph,Time complexity,Mathematics | Conference |
Volume | ISSN | ISBN |
3595 | 0302-9743 | 3-540-28061-8 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Xiaomin Chen | 1 | 43 | 6.18 |
Mario Szegedy | 2 | 3358 | 325.80 |
Lei Wang | 3 | 75 | 9.10 |