---
_id: '13165'
abstract:
- lang: eng
  text: "A graph G=(V, E) is called fully regular if for every independent set I c
    V, the number of vertices in V\\I  that are not connected to any element of I
    depends only on the size of I. A linear ordering of the vertices of G is called
    successive if for every i, the first i vertices induce a connected subgraph of
    G. We give an explicit formula for the number of successive vertex orderings of
    a fully regular graph.\r\nAs an application of our results, we give alternative
    proofs of two theorems of Stanley and Gao & Peng, determining the number of linear
    edge orderings of complete graphs and complete bipartite graphs, respectively,
    with the property that the first i edges induce a connected subgraph.\r\nAs another
    application, we give a simple product formula for the number of linear orderings
    of the hyperedges of a complete 3-partite 3-uniform hypergraph such that, for
    every i, the first i hyperedges induce a connected subgraph. We found similar
    formulas for complete (non-partite) 3-uniform hypergraphs and in another closely
    related case, but we managed to verify them only when the number of vertices is
    small."
article_number: '105776'
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Lixing
  full_name: Fang, Lixing
  last_name: Fang
- first_name: Hao
  full_name: Huang, Hao
  last_name: Huang
- first_name: János
  full_name: Pach, János
  id: E62E3130-B088-11EA-B919-BF823C25FEA4
  last_name: Pach
- first_name: Gábor
  full_name: Tardos, Gábor
  last_name: Tardos
- first_name: Junchi
  full_name: Zuo, Junchi
  last_name: Zuo
citation:
  ama: Fang L, Huang H, Pach J, Tardos G, Zuo J. Successive vertex orderings of fully
    regular graphs. <i>Journal of Combinatorial Theory Series A</i>. 2023;199(10).
    doi:<a href="https://doi.org/10.1016/j.jcta.2023.105776">10.1016/j.jcta.2023.105776</a>
  apa: Fang, L., Huang, H., Pach, J., Tardos, G., &#38; Zuo, J. (2023). Successive
    vertex orderings of fully regular graphs. <i>Journal of Combinatorial Theory.
    Series A</i>. Elsevier. <a href="https://doi.org/10.1016/j.jcta.2023.105776">https://doi.org/10.1016/j.jcta.2023.105776</a>
  chicago: Fang, Lixing, Hao Huang, János Pach, Gábor Tardos, and Junchi Zuo. “Successive
    Vertex Orderings of Fully Regular Graphs.” <i>Journal of Combinatorial Theory.
    Series A</i>. Elsevier, 2023. <a href="https://doi.org/10.1016/j.jcta.2023.105776">https://doi.org/10.1016/j.jcta.2023.105776</a>.
  ieee: L. Fang, H. Huang, J. Pach, G. Tardos, and J. Zuo, “Successive vertex orderings
    of fully regular graphs,” <i>Journal of Combinatorial Theory. Series A</i>, vol.
    199, no. 10. Elsevier, 2023.
  ista: Fang L, Huang H, Pach J, Tardos G, Zuo J. 2023. Successive vertex orderings
    of fully regular graphs. Journal of Combinatorial Theory. Series A. 199(10), 105776.
  mla: Fang, Lixing, et al. “Successive Vertex Orderings of Fully Regular Graphs.”
    <i>Journal of Combinatorial Theory. Series A</i>, vol. 199, no. 10, 105776, Elsevier,
    2023, doi:<a href="https://doi.org/10.1016/j.jcta.2023.105776">10.1016/j.jcta.2023.105776</a>.
  short: L. Fang, H. Huang, J. Pach, G. Tardos, J. Zuo, Journal of Combinatorial Theory.
    Series A 199 (2023).
corr_author: '1'
date_created: 2023-06-25T22:00:45Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2025-09-09T12:30:39Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1016/j.jcta.2023.105776
external_id:
  arxiv:
  - '2206.13592'
  isi:
  - '001144487800001'
file:
- access_level: open_access
  checksum: 9eebc213b4182a66063a99083ff5bd04
  content_type: application/pdf
  creator: dernst
  date_created: 2024-01-30T12:03:10Z
  date_updated: 2024-01-30T12:03:10Z
  file_id: '14902'
  file_name: 2023_JourCombinatiorialTheory_Fang.pdf
  file_size: 352555
  relation: main_file
  success: 1
file_date_updated: 2024-01-30T12:03:10Z
has_accepted_license: '1'
intvolume: '       199'
isi: 1
issue: '10'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-sa/4.0/
month: '10'
oa: 1
oa_version: Published Version
publication: Journal of Combinatorial Theory. Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Successive vertex orderings of fully regular graphs
tmp:
  image: /images/cc_by_nc_sa.png
  legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
  name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
    BY-NC-SA 4.0)
  short: CC BY-NC-SA (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 199
year: '2023'
...