Point partition numbers and generalized Nordhaus-Gaddum problems
Point-distinguishing chromatic index of the union of paths
Let be a simple graph. For a general edge coloring of a graph (i.e., not necessarily a proper edge coloring) and a vertex of , denote by the set (not a multiset) of colors used to color the edges incident to . For a general edge coloring of a graph , if for any two different vertices and of , then we say that is a point-distinguishing general edge coloring of . The minimum number of colors required for a point-distinguishing general edge coloring of , denoted by , is called...
Point-set domatic numbers of graphs
A subset of the vertex set of a graph is called point-set dominating, if for each subset there exists a vertex such that the subgraph of induced by is connected. The maximum number of classes of a partition of , all of whose classes are point-set dominating sets, is the point-set domatic number of . Its basic properties are studied in the paper.
Poisson convergence of numbers of vertices of a given degree in random graphs
The asymptotic distributions of the number of vertices of a given degree in random graphs, where the probabilities of edges may not be the same, are given. Using the method of Poisson convergence, distributions in a general and particular cases (complete, almost regular and bipartite graphs) are obtained.
Poisson kernels of drifted Laplace operators on trees and on the half-plane
Starting with the computation of the appropriate Poisson kernels, we review, complement, and compare results on drifted Laplace operators in two different contexts: homogeneous trees and the hyperbolic half-plane.
Poisson matching
Suppose that red and blue points occur as independent homogeneous Poisson processes in ℝd. We investigate translation-invariant schemes for perfectly matching the red points to the blue points. For any such scheme in dimensions d=1, 2, the matching distance X from a typical point to its partner must have infinite d/2th moment, while in dimensions d≥3 there exist schemes where X has finite exponential moments. The Gale–Shapley stable marriage is one natural matching scheme, obtained by iteratively...
Polar coordinate drawing of planar graphs with good angular resolution.
Polar graphs and railway traffic
Polarities of G. Higman's symmetric design and a strongly regular graph on 176 vertices.
Pólya's permanent problem.
Polyèdres finis de dimension 2 à courbure et de rang 2
On définit localement la notion de polyèdre de rang deux pour un polyèdre fini de dimension deux à courbure négative ou nulle. On montre que le revêtement universel d’un tel espace est soit le produit de deux arbres, soit un immeuble de Tits euclidien de rang deux.
Polynomial time algorithms for two classes of subgraph problem
We design a O(n3) polynomial time algorithm for finding a (k-1)- regular subgraph in a k-regular graph without any induced star K1,3(claw-free). A polynomial time algorithm for finding a cubic subgraph in a 4-regular locally connected graph is also given. A family of k-regular graphs with an induced star K1,3 (k even, k ≥ 6), not containing any (k-1)-regular subgraph is also constructed.
Polynomial-time partition of a graph into cliques.
Polypodic codes
Word and tree codes are studied in a common framework, that of polypodes which are sets endowed with a substitution like operation. Many examples are given and basic properties are examined. The code decomposition theorem is valid in this general setup.
Polypodic codes
Word and tree codes are studied in a common framework, that of polypodes which are sets endowed with a substitution like operation. Many examples are given and basic properties are examined. The code decomposition theorem is valid in this general setup.
Polytopic locally linear graphs
Porous media equation on locally finite graphs
In this paper, we consider two typical problems on a locally finite connected graph. The first one is to study the Bochner formula for the Laplacian operator on a locally finite connected graph. The other one is to obtain global nontrivial nonnegative solution to porous-media equation via the use of Aronson-Benilan argument. We use the curvature dimension condition to give a characterization two point graph. We also give a porous-media equation criterion about stochastic completeness of the graph....
Positive knots, closed braids and the Jones polynomial
Using the recent Gauß diagram formulas for Vassiliev invariants of Polyak-Viro-Fiedler and combining these formulas with the Bennequin inequality, we prove several inequalities for positive knots relating their Vassiliev invariants, genus and degrees of the Jones polynomial. As a consequence, we prove that for any of the polynomials of Alexander/Conway, Jones, HOMFLY, Brandt-Lickorish-Millett-Ho and Kauffman there are only finitely many positive knots with the same polynomial and no positive knot...
Positive Q-matrices of graphs
The Q-matrix of a connected graph = (V,E) is , where ∂(x,y) is the graph distance. Let q() be the range of q ∈ (-1,1) for which the Q-matrix is strictly positive. We obtain a sufficient condition for the equality q(̃) = q() where ̃ is an extension of a finite graph by joining a square. Some concrete examples are discussed.
Positivity of the -system cluster algebra.