New formulae for the bipartite vertex frustration and decycling number of graphs

Fayun Cao, Han Ren and Hanlin Chen

Applied Mathematics and Computation, 2019, vol. 347, issue C, 101-112

Abstract: Let ∇2(G), φ(G) and ∇(G) denote the bipartite vertex frustration, bipartite edge frustration and decycling number of a graph G, respectively. In this paper, we show that ∇2(G)=|V(G)|−max{α(G−E(B)):B is a spanning bipartite subgraph of G}, which provides a new method to estimate the bipartite vertex frustration in terms of bipartite edge frustration for graphs. Using the formula above and some known results on the bipartite edge frustration, we derive several new results on the bipartite vertex frustration, including some that are equalities. Further, we study the bipartite vertex frustration of five classes of composite graphs. Finally, we present a formula for the decycling number: ∇(G)=|V(G)|−max{α(G−E(F)):FisaspanningforstofG}. Based on this result, we determine the decycling numbers of many certain graphs. In addition, this formula gives a new way for dealing with the decycling number problem of dense graphs.

Keywords: Bipartite vertex frustration; Bipartite edge frustration; Decycling number; Composite graph (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300318309561
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:347:y:2019:i:c:p:101-112

DOI: 10.1016/j.amc.2018.10.082

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().