On a characterization of graphs by average labellings
Matúš Harminc (1997)
Discussiones Mathematicae Graph Theory
Similarity:
The additive hereditary property of linear forests is characterized by the existence of average labellings.
Matúš Harminc (1997)
Discussiones Mathematicae Graph Theory
Similarity:
The additive hereditary property of linear forests is characterized by the existence of average labellings.
Mieczysław Borowiecki, Izak Broere, Marietjie Frick, Peter Mihók, Gabriel Semanišin (1997)
Discussiones Mathematicae Graph Theory
Similarity:
In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.
Gabriel Semanišin (2002)
Discussiones Mathematicae Graph Theory
Similarity:
A natural generalization of the fundamental graph vertex-colouring problem leads to the class of problems known as generalized or improper colourings. These problems can be very well described in the language of reducible (induced) hereditary properties of graphs. It turned out that a very useful tool for the unique determination of these properties are generating sets. In this paper we focus on the structure of specific generating sets which provide the base for the proof of The Unique...
Alekseev, Vladimir E., Farrugia, Alastair, Lozin, Vadim V. (2004)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Amelie J. Berger (2001)
Discussiones Mathematicae Graph Theory
Similarity:
A property of graphs is any class of graphs closed under isomorphism. Let ₁,₂,...,ₙ be properties of graphs. A graph G is (₁,₂,...,ₙ)-partitionable if the vertex set V(G) can be partitioned into n sets, V₁,V₂,..., Vₙ, such that for each i = 1,2,...,n, the graph . We write ₁∘₂∘...∘ₙ for the property of all graphs which have a (₁,₂,...,ₙ)-partition. An additive induced-hereditary property is called reducible if there exist additive induced-hereditary properties ₁ and ₂ such that = ₁∘₂....
Amanda Niedzialomski (2016)
Discussiones Mathematicae Graph Theory
Similarity:
For k ∈ ℤ+ and G a simple, connected graph, a k-radio labeling f : V (G) → ℤ+ of G requires all pairs of distinct vertices u and v to satisfy |f(u) − f(v)| ≥ k + 1 − d(u, v). We consider k-radio labelings of G when k = diam(G). In this setting, f is injective; if f is also surjective onto {1, 2, . . . , |V (G)|}, then f is a consecutive radio labeling. Graphs that can be labeled with such a labeling are called radio graceful. In this paper, we give two results on the existence of radio...
Akiyama, Jin, Harary, Frank (1979)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Chandran, L.Sunil, Lozin, Vadim V., Subramanian, C.R. (2005)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Dalibor Fronček (2008)
Discussiones Mathematicae Graph Theory
Similarity:
In this paper we describe a natural extension of the well-known ρ-labeling of graphs (also known as rosy labeling). The labeling, called product rosy labeling, labels vertices with elements of products of additive groups. We illustrate the usefulness of this labeling by presenting a recursive construction of infinite families of trees decomposing complete graphs.
Mieczysław Borowiecki, Danuta Michalak, Elżbieta Sidorowicz (1997)
Discussiones Mathematicae Graph Theory
Similarity:
The purpose of this paper is to present some basic properties of 𝓟-dominating, 𝓟-independent, and 𝓟-irredundant sets in graphs which generalize well-known properties of dominating, independent and irredundant sets, respectively.
Mekkia Kouider, Preben Dahl Vestergaard (2004)
Discussiones Mathematicae Graph Theory
Similarity:
Let a and b be integers 4 ≤ a ≤ b. We give simple, sufficient conditions for graphs to contain an even [a,b]-factor. The conditions are on the order and on the minimum degree, or on the edge-connectivity of the graph.
Mieczysław Borowiecki, Arnfried Kemnitz, Massimiliano Marangio, Peter Mihók (2011)
Discussiones Mathematicae Graph Theory
Similarity:
An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let P and Q be additive hereditary properties of graphs. A (P,Q)-total coloring of a simple graph G is a coloring of the vertices V(G) and edges E(G) of G such that for each color i the vertices colored by i induce a subgraph of property P, the edges colored by i induce a subgraph of property Q and incident vertices and edges obtain different colors. In this...
Zlatomir Lukić (1982)
Publications de l'Institut Mathématique
Similarity:
Shariefuddin, Pirzada, Merajuddin, Pirzada (1996)
Novi Sad Journal of Mathematics
Similarity:
Norbert Polat (2003)
Discussiones Mathematicae Graph Theory
Similarity:
A class C of graphs is said to be dually compact closed if, for every infinite G ∈ C, each finite subgraph of G is contained in a finite induced subgraph of G which belongs to C. The class of trees and more generally the one of chordal graphs are dually compact closed. One of the main part of this paper is to settle a question of Hahn, Sands, Sauer and Woodrow by showing that the class of bridged graphs is dually compact closed. To prove this result we use the concept of constructible...