Optimally Balanced Forward Degree Sequence
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.
Xiaomin Chen Maxio Szegedy Lei Wang
Department of Computer Science, Rutgers University
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
680-689
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）