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.
Alekseev, Vladimir E., Farrugia, Alastair, Lozin, Vadim V. (2004)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Farrugia, Alastair (2004)
The Electronic Journal of Combinatorics [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 = ₁∘₂....
Jan Kratochvíl, Ingo Schiermeyer (1997)
Discussiones Mathematicae Graph Theory
Similarity:
We prove that for any additive hereditary property P > O, it is NP-hard to decide if a given graph G allows a vertex partition V(G) = A∪B such that G[A] ∈ 𝓞 (i.e., A is independent) and G[B] ∈ P.
Roger Crocker (1969)
Colloquium Mathematicae
Similarity:
Piroska Lakatos (2001)
Colloquium Mathematicae
Similarity:
The motivation for considering positive additive functions on trees was a characterization of extended Dynkin graphs (see I. Reiten [R]) and applications of additive functions in representation theory (see H. Lenzing and I. Reiten [LR] and T. Hübner [H]). We consider graphs equipped with integer-valued functions, i.e. valued graphs (see also [DR]). Methods are given for constructing additive functions on valued trees (in particular on Euclidean graphs) and for characterizing...
I. Kátai (1977)
Colloquium Mathematicae
Similarity:
W. Narkiewicz (1974)
Colloquium Mathematicae
Similarity:
Amelie Berger, Izak Broere (1999)
Discussiones Mathematicae Graph Theory
Similarity:
Let H be a fixed finite graph and let → H be a hom-property, i.e. the set of all graphs admitting a homomorphism into H. We extend the definition of → H to include certain infinite graphs H and then describe the minimal reducible bounds for → H in the lattice of additive hereditary properties and in the lattice of hereditary properties.
Karol Baron (2017)
Annales Mathematicae Silesianae
Similarity:
Let E be a separable real inner product space of dimension at least 2 and V be a metrizable and separable linear topological space. We show that the set of all orthogonally additive functions mapping E into V and having big graphs is dense in the space of all orthogonally additive functions from E into V with the Tychonoff topology.
Peter Mihók, Gabriel Semanišin (2011)
Discussiones Mathematicae Graph Theory
Similarity:
The concept of an object-system is a common generalization of simple graph, digraph and hypergraph. In the theory of generalised colourings of graphs, the Unique Factorization Theorem (UFT) for additive induced-hereditary properties of graphs provides an analogy of the well-known Fundamental Theorem of Arithmetics. The purpose of this paper is to present UFT for object-systems. This result generalises known UFT for additive induced-hereditary and hereditary properties of graphs and digraphs....
L. Drewnowski (1978)
Colloquium Mathematicae
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.
Bogdan Pawlik (1987)
Colloquium Mathematicae
Similarity:
Gurusamy Rengasamy Vijayakumar (2013)
Discussiones Mathematicae Graph Theory
Similarity:
The infimum of the least eigenvalues of all finite induced subgraphs of an infinite graph is defined to be its least eigenvalue. In [P.J. Cameron, J.M. Goethals, J.J. Seidel and E.E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976) 305-327], the class of all finite graphs whose least eigenvalues ≥ −2 has been classified: (1) If a (finite) graph is connected and its least eigenvalue is at least −2, then either it is a generalized line graph or it is represented...
Peter Mihók, Janka Oravcová, Roman Soták (2011)
Discussiones Mathematicae Graph Theory
Similarity:
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...
Walter Carballosa, Ruy Fabila-Monroy, Jesús Leaños, Luis Manuel Rivera (2017)
Discussiones Mathematicae Graph Theory
Similarity:
Let G = (V, E) be a graph of order n and let 1 ≤ k < n be an integer. The k-token graph of G is the graph whose vertices are all the k-subsets of V, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper we characterize precisely, for each value of k, which graphs have a regular k-token graph and which connected graphs have a planar k-token graph.