IJPAM: Volume 116, No. 2 (2017)

Title

THE DECYCLING NUMBER OF
$(n,k)$-ARRANGEMENT GRAPHS $A_{n,k}$

Authors

Xirong Xu$^1$, Huifeng Zhang$^2$, Sijia Zhang$^3$,
Lingqi Zhao$^4$, Ziqi Pan$^5$, Baocai Wang$^6$
$^{1,2,5,6}$School of Computer Science and Technology
Dalian University of Technology
Dalian, 116024, P.R. CHINA
$^3$School of Information Engineering
Dalian Ocean University
Dalian, 116023, P.R. CHINA
$^4$Department of Computer Science and Computing Center
Inner Mongolia University for Nationalities
Inner Mongolia, P.R. CHINA

Abstract

A subset $F\subset V(G)$ is called a decycling set if the subgraph $G-F$ is acyclic. The minimum cardinality of a decycling set is called the decycling number of $G$, which is proposed by Beineke and Vandell [1]. In this paper, we consider a particular topology graph called the $(n,k)$-arrangement graph $A_{n,k}$. We use $\nabla(A_{n,k})$ to denote the decycling number of $A_{n,k}$. This paper proves that

\begin{displaymath}\nabla(A_{n,2})=n(n-3)+1, n\geq 4.\end{displaymath}

History

Received: 2017-05-09
Revised: 2017-06-16
Published: October 7, 2017

AMS Classification, Key Words

AMS Subject Classification: 05C85, 05C85, 68R10
Key Words and Phrases: graph theory, decycling set, decycling number,
$(n,k)$-arrangement graph, acyclic subgraph

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
L. W. Beineke, R. C. Vandell, Decycling graphs, J. Graph Theory,25, 59-77, (1997).

2
P. Erdős, M. Saks, V. T. Sós, Maximum induced trees in graphs.J. Combin. Theory Ser. B., 41, 61-79, (1986).

3
S. Bau and L. W. Beineke, The decycling number of graphs, Australas.J. Combin. 25, 285-298,(2002).

4
M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide tothe Theory of NP-completeness, Freeman, San Francisco, CA, 1979.

5
M. R. Garey and D. S. Johnson, Computers and Intractability, Aguide to the theory of NP-completeness. A Series of Books in theMathematical Sciences. W. H. Freeman and Co., 1979. x+338 pp. ISBN:0-7167-1045-5.

6
V. Bafna, P. Berman and T. Fujito, A 2-approximation algorithm forthe undirected feedback vertex set problem, SIAM J. Discrete Math.12, 289-297, (1999).

7
A.Shamir, A linear time algorithm for finding minimum reduciblegraphs, SIAM J.Comput., 8(4), 645-655, (1979).

8
Y.D.Liang, M.S.Chang, Minimum feedback vertex set in cocomparabilityand convex bipartite graphs, Acta Inform., 34(5), 337-346,(1997).

9
C. Wang, E.L. Lloyd, M.L. Sofra, Feedback vertex sets and cyclicallyreducible graphs, J. ACM, 32(2), 296-313, (1985).

10
C.L. Lu, C.Y Tang, A linear-time algorithm for the weighted feedbackvertex problem on interval graphs, Information Processing Letters,61(2), 107-111, (1997).

11
R. Focardi, F.L. Luccio, D. Peleg, Feedback vertex set inhypercubes, Information Processing Letters, 76(1-2), 1-5,(2000).

12
Wei-Kuo Chiang, Rong-Jaye Chen, On the arrangement graph.Information Processing Letters, 66, 215-219, (1998).

13
Wei-Kuo Chiang, Rong-Jaye Chen, The (n,k)-star graph: A generalizedstar graph. National Chiao Tung University, Taiwan, (1994).

14
Fu-Hsing Wang, Yue-Li Wang, Jou-Ming Chang, Feedback vertex sets in star graphs.Information Processing Letters, 89, 203-208, (2004).

15
F.-H. Wang, C.-J. Hsu, J.-C. Tsai, Minimal feedback vertex sets indirected split-stars. Networks, 45, 218-223, (2005).

16
J.-M. Xu, Topological Structure and Analysis of InterconnectionNetworks. Kluwer Academic Publishers, Dordrecht/Boston/London,(2001).

17
X.-R. Xu, Y.-C. Cao, J.-M. Xu, Y.-Z. Wu, Feedback numbers of DeBruijn Digraphs. Computer and Mathematics with Applications, 59, 716-723, (2010).

18
X.-R. Xu, J.-M. Xu, Y.-C. Cao, Bounds on Feedback Numbers of DeBruijn Graphs. Taiwanese Journal of Mathematics, 15(3),1101-1113, (2011).

19
J.-M. Xu, Y.-Z. Wu, J. Huang, C. Yang, Feedback numbers of Kautzdigraphs, Discrete Math., 307(13),1589-1599,(2007).

20
J. Wang, X.-R. Xu, D.-J. Zhu, L.-Q. Gao, J.-M. Xu, On the bounds offeedback numbers of (n,k)-star graphs. Information ProcessingLetters, 112, 473-478,(2012).

21
X.-R. Xu, J. Wang, J.-M. Xu, Y.-C. Cao, Feedback numbers of Kautzundirected graphs, Australasian Journal of Combinatorics, 52,3-9,(2012).

22
L.-Q. Gao, X.-R. Xu, J. Wang, D.J.Zhu, Y.S. Yang, The decycling number of generalizedPetersen graphs, Discrete Applied Mathematics, 181,297-300,(2015).

23
S.-J. Zhang, X.-R.Xu, C. Yin, N.Cao, Y.S. Yang, Feedback Numbers ofAugmented Cubes $AQ_{n}$, Utilitas Mathematica, 97,183-192,(2015).

24
J. Wang, X.-R. Xu, L.-Q. Gao, S.-J. Zhang, Y.S. Yang, Decycling bubble sort graphs,Discrete Applied Mathematics, 194, 178-182,(2015).

How to Cite?

DOI: 10.12732/ijpam.v116i2.15 How to cite this paper?

Source:
International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2017
Volume: 116
Issue: 2
Pages: 437 - 446


$(n,k)$-ARRANGEMENT GRAPHS $A_{n,k}$%22&as_occt=any&as_epq=&as_oq=&as_eq=&as_publication=&as_ylo=&as_yhi=&as_sdtAAP=1&as_sdtp=1" title="Click to search Google Scholar for this entry" rel="nofollow">Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).