University of IsfahanTransactions on Combinatorics2251-865711120220301Vertex decomposability of complexes associated to forests1132565410.22108/toc.2021.127059.1809ENAnuragSinghDepartment of Mathematics, Chennai Mathematical Institute, Kelambakkam, Chennai, India0000-0003-0497-4841Journal Article20210117In this article, we discuss the vertex decomposability of three well-studied simplicial complexes associated to forests. In particular, we show that the bounded degree complex of a forest and the complex of directed trees of a multidiforest is vertex decomposable. We then prove that the non-cover complex of a forest is either contractible or homotopy equivalent to a sphere. Finally we provide a complete characterization of forests whose non-cover complexes are vertex decomposable.https://toc.ui.ac.ir/article_25654_6acf776ce2921143525fd1fb0237d77b.pdfUniversity of IsfahanTransactions on Combinatorics2251-865711120220301An effective new heuristic algorithm for solving permutation flow shop scheduling problem15272541910.22108/toc.2021.126406.1795ENShahriarFarahmand RadDepartment of Mathematics, Payame Noor University of ABCD, P.O.Box 19395-3697, Tehran, IranJournal Article20201210The deterministic permutation flow shop scheduling problem with makespan criterion is not solvable in polynomial time. Therefore, researchers have thought about heuristic algorithms. There are many heuristic algorithms for solving it that is a very important combinatorial optimization problem. In this paper, a new algorithm is proposed for solving the mentioned problem. The presented algorithm chooses the weighted path that starts from the up-left corner and reaches the down-right in the matrix of jobs processing times and calculates the biggest sum of the times in the footprints of this path. The row with the biggest sum permutes among all the rows of the matrix for locating the minimum of makespan. This method was run on Taillard’s standard benchmark and the solutions were compared with the optimum or the best ones as well as 14 famous heuristics. The validity and effectiveness of the algorithm are shown with tables and statistical evaluation.https://toc.ui.ac.ir/article_25419_e602a948cb2cd8fdf03ff1639a347014.pdfUniversity of IsfahanTransactions on Combinatorics2251-865711120220301On the VC-dimension, covering and separating properties of the cycle and spanning tree hypergraphs of graphs29432574610.22108/toc.2021.127880.1832ENAlirezaMofidiDepartment of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Poly-
technic), Hafez Avenue, 15194, Tehran, IranJournal Article20210319In this paper, we delve into studying some relations between the structure of the cycles and spanning trees of a graph through the lens of its cycle and spanning tree hypergraphs which are hypergraphs with the edge set of the graph as their vertices and the edge sets of the cycles and spanning trees as their hyperedges respectively. In particular, we investigate relations between these hypergraphs from the perspective of the VC-dimension and some important separating and covering features of hypergraph theory and amongst the results, for example show that the VC-dimension of the cycle hypergraph is less than or equal to the VC-dimension of the spanning tree hypergraph and their gap can be arbitrary large. Note that VC-dimension is an important measure of complexity and a fundamental notion in numerous fields such as extremal combinatorics, graph theory, statistics and the theory of machine learning. Also we compare the separating and covering features of the mentioned hypergraphs and for instance show that the separating number of the cycle hypergraph is less than or equal to that of the spanning tree hypergraph. These hypergraphs help us to make several connections between cycles and spanning trees of graphs and compare their complexities.https://toc.ui.ac.ir/article_25746_890e066e8b9dd269c189910e7e780475.pdfUniversity of IsfahanTransactions on Combinatorics2251-865711120220301Certain classes of complementary equienergetic graphs45512591410.22108/toc.2021.127167.1816ENHarishchandra S.RamaneDepartment of Mathematics, Karnatak University, Pavate Nagar, Dharwad - 580003, IndiaDaneshwari D.PatilDepartment of Mathematics, Karnatak University, Pavate Nagar, Dharwad - 580003, India0000-0001-8884-5910Kartik S.PiseDepartment of Mathematics, Karnatak University, Pavate Nagar, Dharwad - 580003, India0000-0002-5403-3735Journal Article20210124The energy of a graph is the sum of the absolute values of the eigenvalues of a graph. Two graphs are said to be equienergetic if they have same energy. A graph is said to be complementary equienergetic if it is equienergetic with its complement. Recently several complementary equienergetic graphs have been identified. In this paper, we characterize the cycles, paths, complete bipartite regular graphs and iterated line graphs of regular graphs, which are complementary equienergetic.<br />.https://toc.ui.ac.ir/article_25914_84cb16550fbe408bdebe487a425cfe3a.pdfUniversity of IsfahanTransactions on Combinatorics2251-865711120220301Claw-decomposition of Kneser Graphs53612603510.22108/toc.2021.126283.1792ENSankariCDepartment of Mathematics, A. V. V. M. Sri Pushpam College(Affiliated to Bharathidasan University), Poondi, Than-
javur, Tamil Nadu, India0000-0003-3325-7163SangeethaRDepartment of Mathematics, A. V. V. M. Sri Pushpam College(Affiliated to Bharathidasan University), Poondi, Than-
javur, Tamil Nadu, India0000-0003-2726-0956K.ArthiDepartment of Mathematics, A. V. V. M. Sri Pushpam College( Affiliated to Bharathidasan University), Poondi, Than-
javur, Tamil Nadu, India0000-0002-0399-1343Journal Article20201205A claw is a star with three edges. The Kneser graph $KG_{n,2}$ is the graph whose vertices are the $2$-subsets of an $n$-set, in which two vertices are adjacent if and only if their intersection is empty. In this paper, we prove that $KG_{n,2}$ is claw-decomposable, for all $n \geq 6$.https://toc.ui.ac.ir/article_26035_96affe6636624d4a3ebc38ddb0989312.pdf