(-1)-critical graphs.
From MaRDI portal
Publication:2804805
zbMATH Open1349.05139arXiv1007.2639MaRDI QIDQ2804805FDOQ2804805
Authors: Houmem Belkhechine, Imed Boudabbous, Mohamed Baka Elayech 
Publication date: 4 May 2016
Published in: Ars Combinatoria (Search for Journal in Brave)
Abstract: Given a (directed) graph G=(V,A), a subset X of V is an interval of G provided that for any a, bin X and xin V-X, (a,x)in A if and only if (b,x)in A and (x,a)in A if and only if (x,b)in A. For example, emptyset, {x} (x in V) and V are intervals of G, called trivial intervals. A graph, all the intervals of which are trivial, is indecomposable; otherwise, it is decomposable. A vertex x of an indecomposable graph is critical if G-x is decomposable. In 1993, J.H. Schmerl and W.T. Trotter characterized the indecomposable graphs, all the vertices of which are critical, called critical graphs. In this article, we characterize the indecomposable graphs which admit a single non critical vertex, that we call (-1)-critical graphs.} This gives an answer to a question asked by Y. Boudabbous and P. Ille in a recent article studying the critical vertices in an indecomposable graph.
Full work available at URL: https://arxiv.org/abs/1007.2639
Recommendations
- On \((g,f,n)\)-critical graphs.
- \((a,b,k)\)-critical graphs.
- On \(i^{-}\)-ER-critical graphs
- scientific article; zbMATH DE number 1187326
- A result on \((a,b,k)\)-critical graphs.
- Critical graphs with connected complements
- Critical Hamiltonian connected graphs.
- scientific article; zbMATH DE number 1124609
- Connected domination critical graphs.
- (\(\Delta-k\))-critical graphs
Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (4)
This page was built for publication: \((-1)\)-critical graphs.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2804805)
