TOPICS
Search

Feedback Vertex Set Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The feedback vertex set number, also known as the decycling number (Bau and Beineke 2007), is the size of a smallest feedback vertex set, i.e., a set of vertices which, when removed from the graph (together with any adjacent edges), produces an acyclic graph. It is variously denoted phi (Bau and Beineke 2002) or del (Pike and Zhou 2005, Bau 2007).

Every acyclic graph therefore has feedback vertex set number 0.

The feedback vertex number for a connected graph satisfies

del <=(m-n+1)/(Delta-1),

where n is the vertex count, m the edge count, and Delta the maximum vertex degree (Bau 2007).

Finding the feedback vertex set number of an undirected graph with vertex count n can be solved in time O(1.7347^n) (Fomin and Villanger 2010).

The feedback vertex set numbers are known for some families of graphs, as summarized in the following table, where [x] denotes the ceiling function |_x_| the floor function, and square the graph Cartesian product.

familydel references
antiprism graph Ci_(2n)(1,2)|_(2(n+2))/3_|
book graph K_(n,1) square P_21
cocktail party graph K_(n×2)max(0,2n-1)
complete bipartite graph K_(m,n)min(m,n)-1
complete graph K_nmax(0,2n-2)
complete k-partite graph K_(k_1,k_2,...)(sum_(i)k_i)-(max_(i)k_i)-1
complete tripartite graph K_(k,m,n)k+m+n-max(k,m,n)-1
cycle graph C_n1trivial
empty graph K^__n0trivial
gear graph2
grid graph P_n square P_n[(n^2)/3-n/6+4/4]-[n/2]Alkauskas (2022)
grid graph P_m square P_nclosed forms know for m<=7 and some other casesBau and Beineke (2002), Bau (2007)
Hanoi graph3^(n-1)
helm graph2
ladder graph P_2 square P_n|_n/2_|Bau and Beineke (2002), Bau (2007)
Möbius ladder M_n|_n/2_|+1
path graph P_n0trivial
prism graph C_n square P_2|_n/2_|+1
rook graph K_m square K_n{(m-1)(n-1) for |m-n|<=1; min(m,n)(max(m,n)-2) otherwise
star graph K_(1,n-1)0trivial
torus grid graph C_m square C_n{[(3n)/2] for m=4; [(3m)/2] for n=4; [(mn+2)/3] otherwisetrivial
trapezohedral graph3
wheel graph W_n2

See also

Feedback Vertex Set

Explore with Wolfram|Alpha

References

Alkauskas, G. "Maximal Subsets of n×n Board Without Cycles." 2022. https://klevas.mif.vu.lt/~alkauskas/math/square-sequence-alkauskas.pdf.Bau, S. "The Decycling Numbers of Graphs." 19 Mar 2007. https://arxiv.org/pdf/math/0703544.Bau, S.; and Beineke, L. W. "The Decycling Numbers of Graphs." Australasian J. Combin. 25, 285-298, 2002.Beineke, L. W. and Vandell, R. C. "Decycling Graphs." J. Graph Th. 25, 59-77, 1996.Fomin, F. V. and Villanger, Y. "Finding Induced Subgraphs via Minimal Triangulations." In Proc. 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Vol. 5, pp. 383-394, 2010.Pike, D. A. and Zou, Y. "Decycling Cartesian Products of Two Cycles." SIAM J. Discr. Math. 19, 651-663, 2005.

Cite this as:

Weisstein, Eric W. "Feedback Vertex Set Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/FeedbackVertexSetNumber.html

Subject classifications