The converse of Kelly’s lemma and control-classes in graph reconstruction
We prove a converse of the well-known Kelly’s Lemma. This motivates the introduction of the general notions of -table, -congruence and control-class.
The convexity graph of minimal total dominating functions of a graph
The cost chromatic number and hypergraph parameters
In a graph, by definition, the weight of a (proper) coloring with positive integers is the sum of the colors. The chromatic sum is the minimum weight, taken over all the proper colorings. The minimum number of colors in a coloring of minimum weight is the cost chromatic number or strength of the graph. We derive general upper bounds for the strength, in terms of a new parameter of representations by edge intersections of hypergraphs.
The cover pebbling theorem.
The cover time of deterministic random walks.
The cover-index of infinite graphs.
The crossing number of a projective graph is quadratic in the face-width.
The crossing number of the generalized Petersen graph is four
The crossing number of the generalized Petersen graph
Guy and Harary (1967) have shown that, for , the graph is homeomorphic to the Möbius ladder , so that its crossing number is one; it is well known that is planar. Exoo, Harary and Kabell (1981) have shown hat the crossing number of is three, for Fiorini (1986) and Richter and Salazar (2002) have shown that has crossing number two and that has crossing number , provided . We extend this result by showing that also has crossing number for all .
The crossing numbers of certain Cartesian products
In this article we determine the crossing numbers of the Cartesian products of given three graphs on five vertices with paths.
The crossing numbers of join products of paths with graphs of order four
Kulli and Muddebihal [V.R. Kulli, M.H. Muddebihal, Characterization of join graphs with crossing number zero, Far East J. Appl. Math. 5 (2001) 87-97] gave the characterization of all pairs of graphs which join product is planar graph. The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. There are only few results concerning crossing numbers of graphs obtained as join product of two graphs. In the paper, the exact values of crossing numbers...
The crossing numbers of products of a 5-vertex graph with paths and cycles
There are several known exact results on the crossing numbers of Cartesian products of paths, cycles or stars with "small" graphs. Let H be the 5-vertex graph defined from K₅ by removing three edges incident with a common vertex. In this paper, we extend the earlier results to the Cartesian products of H × Pₙ and H × Cₙ, showing that in the general case the corresponding crossing numbers are 3n-1, and 3n for even n or 3n+1 if n is odd.
The Crossing Numbers of Products of Path with Graphs of Order Six
The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. For the path Pn of length n, the crossing numbers of Cartesian products G⃞Pn for all connected graphs G on five vertices are also known. In this paper, the crossing numbers of Cartesian products G⃞Pn for graphs G of order six are studied. Let H denote the unique tree of order six with two vertices of degree three. The main contribution is that the crossing number of the Cartesian...
The crossing numbers of some generalized Petersen graphs.
The cube polynomial and its derivatives: The case of median graphs.
The cubic mapping graph for the ring of Gaussian integers modulo
The article studies the cubic mapping graph of , the ring of Gaussian integers modulo . For each positive integer , the number of fixed points and the in-degree of the elements and in are found. Moreover, complete characterizations in terms of are given in which is semiregular, where is induced by all the zero-divisors of .
The decay number and the maximum genus of a graph
The decomposability of additive hereditary properties of graphs
An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If ₁,...,ₙ are properties of graphs, then a (₁,...,ₙ)-decomposition of a graph G is a partition E₁,...,Eₙ of E(G) such that , the subgraph of G induced by , is in , for i = 1,...,n. We define ₁ ⊕...⊕ ₙ as the property G ∈ : G has a (₁,...,ₙ)-decomposition. A property is said to be decomposable if there exist non-trivial hereditary properties ₁ and ₂ such that = ₁⊕ ₂....
The Decomposition of a Digraph into Isotopic Subgraphs
The Decomposition of a General Graph according to a Given Abelian Group