Editing Glossary of graph theory (section)

==P==
{{glossary}}

{{term|parent}}
{{defn|In a rooted tree, a parent of a vertex {{mvar|v}} is a neighbor of {{mvar|v}} along the incoming edge, the one that is directed toward the root.}}

{{term|path}}
{{defn|A [[Path (graph theory)|path]] may either be a walk or a walk without repeated vertices and consequently edges (also called a simple path), depending on the source. Important special cases include [[induced path]]s and [[shortest path]]s.}}

{{term|path decomposition}}
{{defn|A [[path decomposition]] of a graph {{mvar|G}} is a tree decomposition whose underlying tree is a path. Its width is defined in the same way as for tree decompositions, as one less than the size of the largest bag. The minimum width of any path decomposition of {{mvar|G}} is the pathwidth of {{mvar|G}}.}}

{{term|pathwidth}}
{{defn|The [[pathwidth]] of a graph {{mvar|G}} is the minimum width of a path decomposition of {{mvar|G}}. It may also be defined in terms of the clique number of an interval completion of {{mvar|G}}. It is always between the bandwidth and the treewidth of {{mvar|G}}. It is also known as interval thickness, vertex separation number, or node searching number.}}

{{term|pendant}}
{{defn|See {{gli|leaf}}.}}

{{term|perfect}}
{{defn|no=1|A [[perfect graph]] is a graph in which, in every induced subgraph, the chromatic number equals the clique number. The [[perfect graph theorem]] and [[strong perfect graph theorem]] are two theorems about perfect graphs, the former proving that their complements are also perfect and the latter proving that they are exactly the graphs with no odd holes or anti-holes.}}
{{defn|no=2|A [[perfectly orderable graph]] is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with this ordering optimally colors every induced subgraph. The perfectly orderable graphs are a subclass of the perfect graphs.}}
{{defn|no=3|A [[perfect matching]] is a matching that saturates every vertex; see {{gli|matching}}.}}
{{defn|no=4|A perfect [[1-factorization]] is a partition of the edges of a graph into perfect matchings so that each two matchings form a Hamiltonian cycle.}}

{{term|peripheral}}
{{defn|no=1|A [[peripheral cycle]] or non-separating cycle is a cycle with at most one bridge.}}
{{anchor|peripheral vertex}}{{defn|no=2|A peripheral vertex is a vertex whose {{gli|eccentricity}} is maximum. In a tree, this must be a leaf.}}

{{term|Petersen}}
{{defn|no=1|[[Julius Petersen]] (1839–1910), Danish graph theorist.}}
{{defn|no=2|The [[Petersen graph]], a 10-vertex 15-edge graph frequently used as a counterexample.}}
{{defn|no=3|[[Petersen's theorem]] that every bridgeless cubic graph has a perfect matching.}}

{{term|planar}}
{{defn|A [[planar graph]] is a graph that has an [[graph embedding|embedding]] onto the Euclidean plane. A plane graph is a planar graph for which a particular embedding has already been fixed. A {{mvar|k}}-planar graph is one that can be drawn in the plane with at most {{mvar|k}} crossings per edge.}}

{{term|polytree}}
{{defn|A [[polytree]] is an oriented tree; equivalently, a directed acyclic graph whose underlying undirected graph is a tree.}}

{{term|power}}
{{defn|no=1|A [[graph power]] {{math|''G''<sup>''k''</sup>}} of a graph {{mvar|G}} is another graph on the same vertex set; two vertices are adjacent in {{math|''G''<sup>''k''</sup>}} when they are at distance at most {{mvar|k}} in {{mvar|G}}. A [[leaf power]] is a closely related concept, derived from a power of a tree by taking the subgraph induced by the tree's leaves.}}
{{defn|no=2|[[Power graph analysis]] is a method for analyzing complex networks by identifying cliques, bicliques, and stars within the network.}}
{{defn|no=3|[[Power law]]s in the [[degree distribution]]s of [[scale-free network]]s are a phenomenon in which the number of vertices of a given degree is proportional to a power of the degree.}}

{{term|predecessor}}
{{defn|A {{gli|vertex}} coming before a given vertex in a {{gli|directed path}}.}}

{{term|prime}}
{{defn|no=1|A [[prime graph]] is defined from an algebraic [[group (mathematics)|group]], with a vertex for each [[prime number]] that divides the order of the group.}}
{{defn|no=2|In the theory of [[modular decomposition]], a prime graph is a graph without any nontrivial modules.}}
{{defn|no=3|In the theory of [[Split (graph theory)|splits]], cuts whose cut-set is a complete bipartite graph, a prime graph is a graph without any splits. Every quotient graph of a maximal decomposition by splits is a prime graph, a star, or a complete graph.}}
{{defn|no=4|A prime graph for the [[Cartesian product of graphs]] is a connected graph that is not itself a product. Every connected graph can be uniquely factored into a Cartesian product of prime graphs.}}

{{term|proper}}
{{defn|no=1|A proper subgraph is a subgraph that removes at least one vertex or edge relative to the whole graph; for finite graphs, proper subgraphs are never isomorphic to the whole graph, but for infinite graphs they can be.}}
{{defn|no=2|A proper coloring is an assignment of colors to the vertices of a graph (a coloring) that assigns different colors to the endpoints of each edge; see {{gli|color}}.}}
{{defn|no=3|A [[proper interval graph]] or proper circular arc graph is an intersection graph of a collection of intervals or circular arcs (respectively) such that no interval or arc contains another interval or arc. Proper interval graphs are also called unit interval graphs (because they can always be represented by unit intervals) or indifference graphs.}}

{{term|property}}
{{defn|A [[graph property]] is something that can be true of some graphs and false of others, and that depends only on the graph structure and not on incidental information such as labels. Graph properties may equivalently be described in terms of classes of graphs (the graphs that have a given property). More generally, a graph property may also be a function of graphs that is again independent of incidental information, such as the size, order, or degree sequence of a graph; this more general definition of a property is also called an invariant of the graph.}}

{{term|pseudoforest}}
{{defn|A [[pseudoforest]] is an undirected graph in which each connected component has at most one cycle, or a directed graph in which each vertex has at most one outgoing edge.}}

{{term|pseudograph}}
{{defn|A pseudograph is a graph or multigraph that allows self-loops.}}

{{glossary end}}