Displaying 221 – 240 of 724

Showing per page

A note on intersection dimensions of graph classes

Petr Hliněný, Aleš Kuběna (1995)

Commentationes Mathematicae Universitatis Carolinae

The intersection dimension of a graph G with respect to a class 𝒜 of graphs is the minimum k such that G is the intersection of some k graphs on the vertex set V ( G ) belonging to 𝒜 . In this paper we follow [ Kratochv’ıl J., Tuza Z.: Intersection dimensions of graph classes, Graphs and Combinatorics 10 (1994), 159–168 ] and show that for some pairs of graph classes 𝒜 , the intersection dimension of graphs from with respect to 𝒜 is unbounded.

A note on joins of additive hereditary graph properties

Ewa Drgas-Burchardt (2006)

Discussiones Mathematicae Graph Theory

Let L a denote a set of additive hereditary graph properties. It is a known fact that a partially ordered set ( L a , ) is a complete distributive lattice. We present results when a join of two additive hereditary graph properties in ( L a , ) has a finite or infinite family of minimal forbidden subgraphs.

A note on kernels and solutions in digraphs

Matúš Harminc, Roman Soták (1999)

Discussiones Mathematicae Graph Theory

For given nonnegative integers k,s an upper bound on the minimum number of vertices of a strongly connected digraph with exactly k kernels and s solutions is presented.

A note on (k,l)-kernels in B-products of graphs

Iwona Włoch (1996)

Discussiones Mathematicae Graph Theory

B-products of graphs and their generalizations were introduced in [4]. We determined the parameters k, l of (k,l)-kernels in generalized B-products of graphs. These results are generalizations of theorems from [2].

A Note on Longest Paths in Circular Arc Graphs

Felix Joos (2015)

Discussiones Mathematicae Graph Theory

As observed by Rautenbach and Sereni [SIAM J. Discrete Math. 28 (2014) 335-341] there is a gap in the proof of the theorem of Balister et al. [Combin. Probab. Comput. 13 (2004) 311-317], which states that the intersection of all longest paths in a connected circular arc graph is nonempty. In this paper we close this gap.

A note on maximal common subgraphs of the Dirac's family of graphs

Jozef Bucko, Peter Mihók, Jean-François Saclé, Mariusz Woźniak (2005)

Discussiones Mathematicae Graph Theory

Let ⁿ be a given set of unlabeled simple graphs of order n. A maximal common subgraph of the graphs of the set ⁿ is a common subgraph F of order n of each member of ⁿ, that is not properly contained in any larger common subgraph of each member of ⁿ. By well-known Dirac’s Theorem, the Dirac’s family ⁿ of the graphs of order n and minimum degree δ ≥ [n/2] has a maximal common subgraph containing Cₙ. In this note we study the problem of determining all maximal common subgraphs of the Dirac’s family...

Currently displaying 221 – 240 of 724