Maximising the number of induced cycles in a graph

Maximising the number of induced cycles in a graph

We determine the maximum number of induced cycles that can be contained in a graph on n ≥ n0 vertices, and show that there is a unique graph that achieves this maximum. This answers a question of Chvátal and Tuza from the 1980s. We also determine the maximum number of odd or even induced cycles that...

書目詳細資料
Main Authors:	Morrison, N, Scott, A
格式:	Journal article
出版:	Elsevier 2017

相似書籍

Maximising the number of cycles in graphs with forbidden subgraphs
由: Morrison, N, et al.
出版: (2020)

Maximising H-colourings of graphs
由: Guggiari, H, et al.
出版: (2019)

Utility Maximisation as a Pathway for Maximisation of Happiness
由: Siddhartha Mitra
出版: (2013-07-01)

Planar Graphs with the Maximum Number of Induced 4-Cycles or 5-Cycles
由: Savery, M
出版: (2024)

on the number of cliques and cycles in graphs
由: Mojgan Emami, et al.
出版: (2013-06-01)

Maximising the size of non-redundant protein datasets using graph theory.
由: Simon C Bull, et al.
出版: (2013-01-01)

MAXIMISING DISCHARGE BURNUP IN AN OPEN CYCLE MOLTEN SALT REACTOR
由: Constable Charlie, et al.
出版: (2021-01-01)

Total resolving number of edge cycle graphs
由: J. Paulraj Joseph, et al.
出版: (2020-09-01)

Skolem Number of Cycles and Grid Graphs
由: Braxton Carrigan, et al.
出版: (2021-08-01)

Enforced maximisation
由: Helm, D, et al.
出版: (1984)

Can we assume that research participants are utility maximisers?
由: Griffith, G, et al.
出版: (2009)

Number of cycles of small length in a graph
由: Sasmita Barik, et al.
出版: (2023-05-01)

Ramsey numbers of cycles versus general graphs
由: Haslegrave, J, et al.
出版: (2023)

Number of cycles in the graph of $312$-avoiding permutations
由: Richard Ehrenborg, et al.
出版: (2014-01-01)

Ramsey numbers of cycles versus general graphs
由: John Haslegrave, et al.
出版: (2023-01-01)

Induced paths in graphs without anticomplete cycles
由: Nguyen, T, et al.
出版: (2023)

Maximising research potential
由: Ian, Jerome Leong
出版: (2016)

The shortest cycle having the maximal number of coalition graphs
由: Andrey A. Dobrynin, et al.
出版: (2024-07-01)

The oriented chromatic number of edge-amalgamation of cycle graph
由: Dina Eka Nurvazly, et al.
出版: (2019-06-01)

Maximising the value of knowledge workers
由: piet Steyn, et al.
出版: (2009-02-01)

On the H-Force Number of Hamiltonian Graphs and Cycle Extendability
由: Hexel Erhard
出版: (2017-02-01)

Maximising the public health benefit of antimalarials.
由: Price, R, et al.
出版: (2010)

Induced subgraphs of graphs with large chromatic number. XI. orientations
由: Chudnovsky, M, et al.
出版: (2018)

On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges
由: Abueida Atif A., et al.
出版: (2014-02-01)

Maximising benefits of student cards
由: Rafidi, Rayyan
出版: (2019)

Maximising the potential of anaerobic digestion
由: Mason, P
出版: (2015)

Maximising the potential of HPV vaccines
由: Jos Luttjeboer, et al.
出版: (2020-04-01)

Induced subgraphs of graphs with large chromatic number IX: rainbow paths
由: Scott, A, et al.
出版: (2017)

Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes
由: Scott, A, et al.
出版: (2018)

Induced subgraphs of graphs with large chromatic number. VI. Banana trees
由: Scott, A, et al.
出版: (2020)

Induced subgraphs of graphs with large chromatic number. XIII. New brooms
由: Scott, A, et al.
出版: (2019)

Induced subgraphs of graphs with large chromatic number. I. Odd holes
由: Scott, A, et al.
出版: (2015)

Lower Bound on the Number of Hamiltonian Cycles of Generalized Petersen Graphs
由: Lu Weihua, et al.
出版: (2020-02-01)

On Local Antimagic Chromatic Number of Cycle-Related Join Graphs
由: Lau Gee-Choon, et al.
出版: (2021-02-01)

Induced subgraphs of graphs with large chromatic number. III. Long holes
由: Chudnovsky, M, et al.
出版: (2016)

Induced subgraphs of graphs with large chromatic number. XII. Distant stars
由: Chudnovsky, M, et al.
出版: (2019)

Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
由: Chudnovsky, M, et al.
出版: (2021)

A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs
由: Olga Bodroža-Pantić, et al.
出版: (2015-03-01)

Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles
由: Michael Haythorpe
出版: (2016-04-01)

Induced subgraphs of graphs with large chromatic number. VII. Gyárfás' complementation conjecture
由: Scott, A, et al.
出版: (2020)