PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 1 | 127-136
Tytuł artykułu

On the Numbers of Cut-Vertices and End-Blocks in 4-Regular Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A cut-vertex in a graph G is a vertex whose removal increases the number of connected components of G. An end-block of G is a block with a single cut-vertex. In this paper we establish upper bounds on the numbers of end-blocks and cut-vertices in a 4-regular graph G and claw-free 4-regular graphs. We characterize the extremal graphs achieving these bounds.
Słowa kluczowe
Wydawca
Rocznik
Tom
34
Numer
1
Strony
127-136
Opis fizyczny
Daty
wydano
2014-02-01
online
2014-02-14
Twórcy
autor
  • Department of Mathematics, Shanghai University, Shanghai 200444, China
  • College of Mathematics Science, Chongqing Normal University Chongqing 400047, China
autor
  • School of Management, Shanghai University, Shanghai 200444, China 2Department of Mathematics, Shanghai University, Shanghai 200444, China, efshan@shu.edu.cn
Bibliografia
  • [1] M.O. Albertson and D.M. Berman, The number of cut-vertices in a graph of given minimum degree, Discrete Math. 89 (1991) 97-100. doi:10.1016/0012-365X(91)90402-N[Crossref]
  • [2] B. Bollobás, Modern Graph Theory (New York, Springer-Verlag, 2001).
  • [3] L.H. Clark and R.C. Entringer, The number of cut vertices in graphs with given minimum degree, Discrete Math. 18 (1990) 137-145. doi:10.1016/0012-365X(90)90145-8[Crossref]
  • [4] K. Nirmala and A.R. Rao, The number of cut vertices in a regular graph, Cahiers Centre Etudes Reserche Oper. 17 (1975) 295-299.
  • [5] N. Achuthan and A.R. Rao, On the number of cut edges in a regular graph, Australas. J. Combin. 27 (2003) 5-12.
  • [6] A. Ramachandra Rao, An extremal problem in graph theory, Israel J. Math. 6 (1968) 261-266. doi:10.1007/BF02760258[Crossref]
  • [7] A. Ramachandra Rao, Some extremal problems and characterizations in the theory of graphs, Ph.D. Thesis, Indian Statistical Institute (1969).
  • [8] S.B. Rao, Contributions to the theory of directed and undirected graphs, Ph.D. Thesis, Indian Statistical Institute (1970).
  • [9] O. Suil and D.B. West, Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree, J. Graph Theory 64 (2010) 116-131. doi:10.1002/jgt.20443 [WoS][Crossref]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1724
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.