All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 39

Showing per page

Gallai's innequality for critical graphs of reducible hereditary properties

Peter Mihók, Riste Skrekovski (2001)

Discussiones Mathematicae Graph Theory

In this paper Gallai’s inequality on the number of edges in critical graphs is generalized for reducible additive induced-hereditary properties of graphs in the following way. Let ₁ , ₂ , . . . , ₖ (k ≥ 2) be additive induced-hereditary properties, = ₁ ∘ ₂ ∘ . . . ∘ ₖ and δ = ∑ i = 1 k δ ( i ) . Suppose that G is an -critical graph with n vertices and m edges. Then 2m ≥ δn + (δ-2)/(δ²+2δ-2)*n + (2δ)/(δ²+2δ-2) unless = ² or G = K δ + 1 . The generalization of Gallai’s inequality for -choice critical graphs is also presented.

Gaps and dualities in Heyting categories

Jaroslav Nešetřil, Aleš Pultr, Claude Tardif (2007)

Commentationes Mathematicae Universitatis Carolinae

We present an algebraic treatment of the correspondence of gaps and dualities in partial ordered classes induced by the morphism structures of certain categories which we call Heyting (such are for instance all cartesian closed categories, but there are other important examples). This allows to extend the results of [14] to a wide range of more general structures. Also, we introduce a notion of combined dualities and discuss the relation of their structure to that of the plain ones.

Generalized circular colouring of graphs

Peter Mihók, Janka Oravcová, Roman Soták (2011)

Discussiones Mathematicae Graph Theory

Let P be a graph property and r,s ∈ N, r ≥ s. A strong circular (P,r,s)-colouring of a graph G is an assignment f:V(G) → {0,1,...,r-1}, such that the edges uv ∈ E(G) satisfying |f(u)-f(v)| < s or |f(u)-f(v)| > r - s, induce a subgraph of G with the propery P. In this paper we present some basic results on strong circular (P,r,s)-colourings. We introduce the strong circular P-chromatic number of a graph and we determine the strong circular P-chromatic number of complete graphs for additive...

Generalized colorings and avoidable orientations

Jenő Szigeti, Zsolt Tuza (1997)

Discussiones Mathematicae Graph Theory

Gallai and Roy proved that a graph is k-colorable if and only if it has an orientation without directed paths of length k. We initiate the study of analogous characterizations for the existence of generalized graph colorings, where each color class induces a subgraph satisfying a given (hereditary) property. It is shown that a graph is partitionable into at most k independent sets and one induced matching if and only if it admits an orientation containing no subdigraph from a family of k+3 directed...

Generalized connectivity of some total graphs

Yinkui Li, Yaping Mao, Zhao Wang, Zongtian Wei (2021)

Czechoslovak Mathematical Journal

We study the generalized k -connectivity κ k ( G ) as introduced by Hager in 1985, as well as the more recently introduced generalized k -edge-connectivity λ k ( G ) . We determine the exact value of κ k ( G ) and λ k ( G ) for the line graphs and total graphs of trees, unicyclic graphs, and also for complete graphs for the case k = 3 .

Generalized Fractional and Circular Total Colorings of Graphs

Arnfried Kemnitz, Massimiliano Marangio, Peter Mihók, Janka Oravcová, Roman Soták (2015)

Discussiones Mathematicae Graph Theory

Let P and Q be additive and hereditary graph properties, r, s ∈ N, r ≥ s, and [ℤr]s be the set of all s-element subsets of ℤr. An (r, s)-fractional (P,Q)-total coloring of G is an assignment h : V (G) ∪ E(G) → [ℤr]s such that for each i ∈ ℤr the following holds: the vertices of G whose color sets contain color i induce a subgraph of G with property P, edges with color sets containing color i induce a subgraph of G with property Q, and the color sets of incident vertices and edges are disjoint. If...

Generalized ramsey theory and decomposable properties of graphs

Stefan A. Burr, Michael S. Jacobson, Peter Mihók, Gabriel Semanišin (1999)

Discussiones Mathematicae Graph Theory

In this paper we translate Ramsey-type problems into the language of decomposable hereditary properties of graphs. We prove a distributive law for reducible and decomposable properties of graphs. Using it we establish some values of graph theoretical invariants of decomposable properties and show their correspondence to generalized Ramsey numbers.

Graph domination in distance two

Gábor Bacsó, Attila Tálos, Zsolt Tuza (2005)

Discussiones Mathematicae Graph Theory

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 D o m D o m u = D o m ₂ u holds for u = all connected graphs without induced P u (u ≥ 2). (In particular, ₂ = K₁ and...

Graphes h - maximaux

M. Chein (1970)

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique

Graphs for n-circular matroids

Renata Kawa (2010)

Discussiones Mathematicae Graph Theory

We give "if and only if" characterization of graphs with the following property: given n ≥ 3, edges of such graphs form matroids with circuits from the collection of all graphs with n fundamental cycles. In this way we refer to the notion of matroidal family defined by Simões-Pereira [2].

Currently displaying 1 – 20 of 39

Page 1 Next