BROWSE

Related Scientist

's photo.

수리 및 계산 과학 연구단
more info

ITEM VIEW & DOWNLOAD

Branch-depth: Generalizing tree-depth of graphs

Cited 0 time in webofscience Cited 0 time in scopus
39 Viewed 0 Downloaded
Title
Branch-depth: Generalizing tree-depth of graphs
Author(s)
Matt DeVos; O-joung Kwon; Sang-il Oum
Publication Date
2020-12
Journal
EUROPEAN JOURNAL OF COMBINATORICS, v.90, pp.103186
Publisher
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
Abstract
© 2020 The Author(s). 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 λ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 ρ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 λG has bounded branch-depth and similarly a class of graphs has bounded shrub-depth if and only if the corresponding class of functions ρ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
URI
https://pr.ibs.re.kr/handle/8788114/7529
DOI
10.1016/j.ejc.2020.103186
ISSN
0195-6698
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse