𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An edge grafting theorem on the energy of unicyclic and bipartite graphs

✍ Scribed by Hai-Ying Shan; Jia-Yu Shao; Fei Gong; Yue Liu

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
159 KB
Volume
433
Category
Article
ISSN
0024-3795

No coin nor oath required. For personal study only.

✦ Synopsis

The energy of a graph is the sum of the absolute values of the eigenvalues of its adjacency matrix. The edge grafting operation on a graph is certain kind of edge moving between two pendant paths starting from the same vertex. In this paper we show how the graph energy changes under the edge grafting operations on unicyclic and bipartite graphs. We also give some applications of this result on the comparison of graph energies between unicyclic or bipartite graphs.

πŸ“œ SIMILAR VOLUMES

NP completeness of the edge precoloring
NP completeness of the edge precoloring extension problem on bipartite graphs
✍ JiΕ™Γ­ Fiala πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 63 KB πŸ‘ 1 views

## Abstract We show that the following problem is __NP__ complete: Let __G__ be a cubic bipartite graph and __f__ be a precoloring of a subset of edges of __G__ using at most three colors. Can __f__ be extended to a proper edge 3‐coloring of the entire graph __G__? This result provides a natural co

Tight upper bound on the number of edges
Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application
✍ Zhi-Zhong Chen; Shiqing Zhang πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 68 KB

We show that an n-vertex bipartite K 3,3 -free graph with n 3 has at most 2n -4 edges and that an n-vertex bipartite K 5 -free graph with n 5 has at most 3n -9 edges. These bounds are also tight. We then use the bound on the number of edges in a K 3,3 -free graph to extend two known NC algorithms fo