Remarks on the Removable Edges of a Spectial Network
It is well-known that the topological structure of an interconnection network can be modeled by a connected graph, whose vertices represent sites of the network and whose edges represent physical communication links. Such a close interrelation between graph theory and network motivates us to investigate the stability of graphs with respect to edge or vertex alteration. Since Tutte gave an instruction of 3connected graphs in 1961, research on structural characterization of connected graph becomes a very popular topic in graph theory. It plays an important role in both theoretical respect and practical applications due to its close connection to network modeling and combinatorial optimization. The concepts of removable edges and contractible edges of graphs are powerful tools to study the structure of graphs and to prove properties of graphs by induction. In this paper we mainly consider the number of removable edges in 3-regular 3-connected graphs whose girth keeps at least 4.
removable edge connected graph regular graph
Jianxiang Cao Minyong Shi
School of Computer Science Communication University of China Beijing, 100024 School of Animation Communication University of China Beijing, 100024
国际会议
昆明、丽江
英文
868-871
2011-04-15（万方平台首次上网日期，不代表论文的发表时间）