Wyniki wyszukiwania

1

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Graphs with small additive stretch number

100%

Rautenbach D.

Discussiones Mathematicae Graph Theory

|

2004

|

tom 24

|

nr 2

291-301

EN

The additive stretch number $s_{add}(G)$ of a graph G is the maximum difference of the lengths of a longest induced path and a shortest induced path between two vertices of G that lie in the same component of G.We prove some properties of minimal forbidden configurations for the induced-hereditary classes of graphs G with $s_{add}(G) ≤ k$ for some k ∈ N₀ = {0,1,2,...}. Furthermore, we derive characterizations of these classes for k = 1 and k = 2.

2

A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs

88%

Metelsky Y., Schemeleva K., Werner F.

Discussiones Mathematicae Graph Theory

|

2017

|

tom 37

|

nr 1

13-28

EN

We characterize the class [...] L32 $L_3^2 $ of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 $L_3^2 $ in the class of threshold graphs, where n is the number of vertices of a tested graph.

3

Dominating bipartite subgraphs in graphs

88%

Bacsó G., Michalak D., Tuza Z.

Discussiones Mathematicae Graph Theory

|

2005

|

tom 25

|

nr 1-2

85-94

EN

A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.

4

Graphs without induced P₅ and C₅

88%

Bacsó G., Tuza Z.

Discussiones Mathematicae Graph Theory

|

2004

|

tom 24

|

nr 3

503-507

EN

Zverovich [Discuss. Math. Graph Theory 23 (2003), 159-162.] has proved that the domination number and connected domination number are equal on all connected graphs without induced P₅ and C₅. Here we show (with an independent proof) that the following stronger result is also valid: Every P₅-free and C₅-free connected graph contains a minimum-size dominating set that induces a complete subgraph.

5

Graph domination in distance two

88%

Bacsó G., Tálos A., Tuza Z.

Discussiones Mathematicae Graph Theory

|

2005

|

tom 25

|

nr 1-2

121-128

EN

Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class 𝓓 of graphs, Domₖ 𝓓 is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ 𝓓 which is also connected. In our notation, Dom𝓓 coincides with Dom₁𝓓. In this paper we prove that $Dom Dom 𝓓_u = Dom₂ 𝓓_u$ holds for $𝓓_u$ = {all connected graphs without induced $P_u$} (u ≥ 2). (In particular, 𝓓₂ = {K₁} and 𝓓₃ = {all complete graphs}.) Some negative examples are also given.

Ograniczanie wyników

5 Discussiones Mathematicae Graph Theory

3 Bacsó G.

3 Tuza Z.

1 Metelsky Y.

1 Michalak D.

1 Rautenbach D.

1 Schemeleva K.

1 Tálos A.

1 Werner F.

1 2017

2 2005

2 2004

Graphs with small additive stretch number

A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs

Dominating bipartite subgraphs in graphs

Graphs without induced P₅ and C₅

Graph domination in distance two