Branch-depth: Generalizing tree-depth of graphs

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 35
  • Download : 8
We present a concept called the branch-depth of a connectivity function, that generalizes the tree-depth of graphs. Then we prove two theorems showing that this concept aligns closely with the notions of tree-depth and shrub-depth of graphs as follows. For a graph G = (V, E) and a subset A of E we let lambda(G)(A) be the number of vertices incident with an edge in A and an edge in E \ A. For a subset X of V, let rho(G)(X) be the rank of the adjacency matrix between X and V \ X over the binary field. We prove that a class of graphs has bounded tree-depth if and only if the corresponding class of functions lambda(G) has bounded branch depth and similarly a class of graphs has bounded shrub-depth if and only if the corresponding class of functions rho(G) has bounded branch-depth, which we call the rank-depth of graphs. Furthermore we investigate various potential generalizations of tree-depth to matroids and prove that matroids representable over a fixed finite field having no large circuits are well-quasi ordered by restriction.
Publisher
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
Issue Date
2020-12
Language
English
Article Type
Article
Citation

EUROPEAN JOURNAL OF COMBINATORICS, v.90

ISSN
0195-6698
DOI
10.1016/j.ejc.2020.103186
URI
http://hdl.handle.net/10203/276402
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
000565160300001.pdf(579.87 kB)Download

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0