In graph theory a graph property is any "inherently graph-theoretical" property of graphs (formal definitions follow), distinguished from properties of graphs described in terms of various graph representations: graph drawings, data structures for graphs, graph labelings, etc. In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects In Mathematics and Computer science, a graph is the basic object of study in Graph theory. Graph drawing, as a branch of Graph theory, applies Topology and Geometry to derive two-dimensional representations of graphs Graph drawing is In Computer science, a graph is a kind of Data structure, specifically an Abstract data type (ADT that consists of a set of nodes (also called In the Mathematical discipline of Graph theory, a graph labeling is the assignment of labels traditionally represented with Integers to the edges

Contents 1 Definitions 2 Graph invariants 3 Types of graph properties 4 See also 5 References

Definitions

While graph drawing and graph representation are valid topics in graph theory, in order to focus on "inherently graph-theoretical" properties of graphs, a graph property is defined to be a property preserved under all possible isomorphisms of a graph. In Graph theory, an isomorphism of graphs G and H is a Bijection between the vertex sets of G and H

Graphs with the same graph property naturally define a certain family of graphs: the ones that have the specified property. Therefore, to avoid the ambiguity of the English word "property" and a feeling of circular logic in the definition, a graph property is defined as a nonempty proper subset of the set of graphs closed under the graph isomorphism. In Logic, begging the question has traditionally described a type of Logical fallacy (also called petitio principii) in which the proposition ^[1]

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".

Formally, a graph invariant is an indexed family of graph properties. In Mathematics, an indexed family of sets is defined in stages beginning with the more general concept of an indexed family of elements, which is really just an alternative

For example "the number of vertices" is an indexed family of graph properties "a graph has M edges, M = 0, 1, 2. . . . ". In this case the family of properties is indexed by the set of nonnegative integer numbers. A more complex example of graph invariant is the degree sequence of a graph: the family of properties is indexed by the set of all ordered sequences of nonnegative integers. In Graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex

Graph invariants

• number of vertices
• number of edges
• vertex chromatic number - minimum number of colors needed to color all vertices so that adjacent vertices have a different color
• edge chromatic number - minimum number of colors needed to color all edges so that adjacent edges have a different color
• edge covering number - minimal number of edges needed to cover all vertices
• vertex covering number - minimal number of vertices needed to cover all edges
• degree sequence
• graph genus

Types of graph properties

• Hereditary property (also called monotone property): a property closed under the operation of taking subgraphs
• Additive graph property: a property closed under the graph union ^[2] For example, being an acyclic graph is an additive property. In Graph theory, graph coloring is a special case of Graph labeling; it is an assignment of labels traditionally called "colors" to elements of a Adjacent is an adjective meaning contiguous, adjoining or abutting. In Graph theory, edge coloring is one type of the Graph coloring problem Adjacent is an adjective meaning contiguous, adjoining or abutting. In the mathematical discipline of Graph theory, a covering (or cover) of a graph is a set of vertices (or edges such that each edge (vertex In the mathematical discipline of Graph theory, a covering (or cover) of a graph is a set of vertices (or edges such that each edge (vertex In Graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex In Topological graph theory, an embedding of a graph G on a Surface &Sigma is a representation of G on &Sigma in which points In Mathematics, a hereditary property is a property of an object that inherits to all its subobjects, where the term subobject depends on the context In Mathematics, a hereditary property is a property of an object that inherits to all its subobjects, where the term subobject depends on the context Operations on graphs produce new graphs from old ones They may be separated into the following major categories Graph theory is a growing area in mathematical research and has a large specialized vocabulary

See also

• Topological index

References

1. ^ Peter Mihok (1999) "Reducible properties and uniquely partitionable graphs" in: Ronald L. In Chemical graph theory and in Mathematical chemistry, a topological index is any of several numerical parameters (which are usually Graph invariants of Graham, "Contemporary Trends in Discrete Mathematics", DIMASC Series in Discrete Mathematics and Computer Science, vol. 49, ISBN 0821809636 p. 213
2. ^ Peter Mihok (1999) "Reducible properties and uniquely partitionable graphs" in: Ronald L. Graham, "Contemporary Trends in Discrete Mathematics", DIMASC Series in Discrete Mathematics and Computer Science, vol. 49, ISBN 0821809636 p. 214

---

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic