Definitions
While graph drawing and graph representation are valid topics in graph theory, in order to focus only on the abstract structure of graphs, a graph property is defined to be a property preserved under all possible isomorphisms of a graph. In other words, it is a property of the graph itself, not of a specific drawing or representation of the graph.
Informally, the term "graph invariant" is used for properties expressed quantitatively, while "property" usually refers to descriptive characterizations of graphs. For example, the statement "graph does not have vertices of degree 1" is a "property" while "the number of vertices of degree 1 in a graph" is an "invariant".
More formally, a graph property is a class of graphs, i.e. a function from graphs to {T,F}, and a graph invariant is a function from graphs to some other set, such as to the natural numbers (for scalar invariants), or to (possibly ordered) sequences of natural numbers (for properties like the degree sequence), or to a polynomial ring, such that isomorphic graphs have the same value.
A graph property is often called hereditary if it also holds for (is "inherited" by) its induced subgraphs. A property is called additive if it is closed under disjoint union. The property of being planar is both hereditary and additive, for example, since a subgraph of a planar graph must be planar, and a disjoint union of two planar graphs must also be planar. The property of being connected is neither, since a subgraph of a connected graph need not be connected, and a disjoint union of two connected graphs cannot be connected.
A graph property is sometimes called monotone increasing (or respectively monotone decreasing) if it is kept under the addition (respectively, the deletion) of edges. For example, the property of being connected is monotone increasing, whereas the property of being 3-colorable is monotone decreasing.
Read more about this topic: Graph Property
Famous quotes containing the word definitions:
“What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
—G.C. (Georg Christoph)
“Lord Byron is an exceedingly interesting person, and as such is it not to be regretted that he is a slave to the vilest and most vulgar prejudices, and as mad as the winds?
There have been many definitions of beauty in art. What is it? Beauty is what the untrained eyes consider abominable.”
—Edmond De Goncourt (1822–1896)
“The loosening, for some people, of rigid role definitions for men and women has shown that dads can be great at calming babies—if they take the time and make the effort to learn how. It’s that time and effort that not only teaches the dad how to calm the babies, but also turns him into a parent, just as the time and effort the mother puts into the babies turns her into a parent.”
—Pamela Patrick Novotny (20th century)