Codes from lattice and related graphs, and permutation decoding

Codes of length n² and dimension 2n−1 or 2n−2 over the field F_p, for any prime p, that can be obtained from designs associated with the complete bipartite graph K_n,n and its line graph, the lattice graph, are examined. The parameters of the codes for all primes are obtained and PD-sets are found for full permutation decoding for all integers n≥3.     

Restricted greedy clique decompositions and greedy clique decompositions ofK 4-free graphs

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. It has recently been shown that any greedy clique decomposition of a graph of ordern has at mostn ²/4 cliques. In this paper, we extend this result by showing that for any positive integerp, 3≤p any clique decomposisitioof a graph of ordern obtained by removing maximal cliques of order at leastp one by one until none remain, in which case the remaining edges are removed one by one, has at mostt _p-1( ⁿ ) cliques. Heret _p-1( ⁿ ) is the number of edges in the Turán graph of ordern, which has no complete subgraphs of orderp. In connection with greedy clique decompositions, P. Winkler conjectured that for any greedy clique decompositionC of a graphG of ordern the sum over the number of vertices in each clique ofC is at mostn ²/2. We prove this conjecture forK ₄-free graphs and show that in the case of equality forC andG there are only two possibilities:

1. G?K _n/2,n/2
2. G is complete 3-partite, where each part hasn/3 vertices.

We show that in either caseC is completely determined.     

On the odd harmonious graphs with applications

The necessary conditions for the existence of odd harmonious labelling of graph are obtained. A cycle C _n is odd harmonious if and only if n≡0 (mod 4). A complete graph K _n is odd harmonious if and only if n=2. A complete k-partite graph K(n ₁,n ₂,…,n _k ) is odd harmonious if and only if k=2. A windmill graph K _n ^t is odd harmonious if and only if n=2. The construction ways of odd harmonious graph are given. We prove that the graph ∨ _i=1 ⁿ G _i , the graph G(+r ₁,+r ₂,…,+r _p ), the graph $\bar{K_{m}}+_{0}P_{n}+_{e}\bar{K_{t}}$ , the graph G∪(X+∪ _k=1 ⁿ Y _k ), some trees and the product graph P _m ×P _n etc. are odd harmonious. The odd harmoniousness of graph can be used to solve undetermined equation.     

On infinite graphs with a specified number of colorings

In this paper we construct a planar graph of degree four which admits exactly N_u 3-colorings, we prove that such a graph must have degree at least four, and we consider various generalizations. We first allow our graph to have either one or two vertices of infinite degree and/or to admit only finitely many colorings and we note how this effects the degrees of the remaining vertices. We next consider n-colorings for n>3, and we construct graphs which we conjecture (but cannot prove) are of minimal degree. Finally, we consider nondenumerable graphs, and for every 3 <n<ω and every infinite cardinal k we construct a graph of cardinality k which admits exactly kn-colorings. We also show that the number of n-colorings of a denumerable graph can never be strictly between N_u and 2^N_u and that an appropriate generalization holds for at least certain nondenumerable graphs.     

The genus of the symmetric quadripartite graph

In this paper the following formula for the genus of the symmetric quadripartite graph is proved. γ(K_n,n,n,n) = (n?1)² for all n≠3.     

Graphs with bounded valency that do not embed in the projective plane

In 1930 Kuratowski proved that a graph does not embed in the real plane R² if and only if it contains a subgraph homeomorphic to one of two graphs, K₅ or K₃₃. Let I_n(P) denote the minimal set of graphs whose vertices have miximal valency n such that any graph which does not embed in the real projective plane (or equivalently, does not embed in the Möbius band) contains a subgraph homeomorphic to a graph in I_n(P) for some positive integer n. Glover and Huneke and Milgram proved that there are only 6 graphs in I₃(P). This note proves that for each n, I_n(P) is finite.     

The set of irreducible graphs for the projective plane is finite

In 1930 Kuratowski proved that a graph does not embed in the real plane R² if and only if it contains a subgraph homeomorphic to one of two graphs, K₅ or K_{3, 3}. For positive integer n, let I_n (P) denote a smallest set of graphs whose maximal valency is n and such that any graph which does not embed in the real projective plane contains a subgraph homeomorphic to a graph in I_n (P) for some n. Glover and Huneke and Milgram proved that there are only 6 graphs in I₃ (P), and Glover and Huneke proved that I_n (P) is finite for all n. This note proves that I_n (P) is empty for all but a finite number of n. Hence there is a finite set of graphs for the projective plane analogous to Kuratowski's two graphs for the plane.     

On the value of a random minimum spanning tree problem

Suppose we are given a complete graph on n vertices in which the lenghts of the edges are independent identically distributed non-negative random variables. Suppose that their common distribution function F is differentiable at zero and D = F′ (0) > 0 and each edge length has a finite mean and variance. Let L_n be the random variable whose value is the length of the minimum spanning tree in such a graph. Then we will prove the following: lim_{n → ∞}E(L_n) = ζ(3)/D where ζ(3) = Σ_{k = 1}^∞ 1/k³ = 1.202… and for any ε > 0 lim_{n → ∞} Pr(|L_n^?ζ(3)/D|) > ε) = 0.     

Group action for enumerating maps on surfaces

A map is a connected topological graph Γ cellularly embedded in a surface. For any connected graph Γ, by introducing the conception of semi-arc automorphism groupAut1/2 Γ and classifying all embedding of Γ under the action of this group, the numbersr ^o (Γ) andr ^N (Γ) of rooted maps on orientable and non-orientable surfaces with underlying graph Γ are found. Many closed formulas without sum Σ for the number of rooted maps on surfaces (orientable or non-orientable) with given underlying graphs, such as, complete graphK _n , complete bipartite graphK _m,n, bouquetsB _n , dipoleDp _n and generalized dipoleDp _n ^k,l are refound in this paper.     

Graph powers and k-ordered Hamiltonicity

It is known that if G is a connected simple graph, then G³ is Hamiltonian (in fact, Hamilton-connected). A simple graph is k-ordered Hamiltonian if for any sequence v₁, v₂,…,v_k of k vertices there is a Hamiltonian cycle containing these vertices in the given order. In this paper, we prove that if k?4, then G^⌊3k/2⌋-2 is k-ordered Hamiltonian for every connected graph G on at least k vertices. By considering the case of the path graph P_n, we show that this result is sharp. We also give a lower bound on the power of the cycle C_n that guarantees k-ordered Hamiltonicity.     

Packing two copies of a tree into its third power

A graph H of order n is said to be k-placeable into a graph G of order n, if G contains k edge-disjoint copies of H. It is well known that any non-star tree T of order n is 2-placeable into the complete graph K_n. In the paper by Kheddouci et al. [Packing two copies of a tree into its fourth power, Discrete Math. 213 (2000) 169-178], it is proved that any non-star tree T is 2-placeable into T⁴. In this paper, we prove that any non-star tree T is 2-placeable into T³.     

Two graph isomorphism polytopes

The convex hull ψ_n,n of certain (n!)² tensors was considered recently in connection with graph isomorphism. We consider the convex hull ψ_n of the n! diagonals among these tensors. We show: 1. The polytope ψ_n is a face of ψ_n,n. 2. Deciding if a graph G has a subgraph isomorphic to H reduces to optimization over ψ_n. 3. Optimization over ψ_n reduces to optimization over ψ_n,n. In particular, this implies that the subgraph isomorphism problem reduces to optimization over ψ_n,n.     

Triangle-free partial graphs and edge covering theorems

In section 1 some lower bounds are given for the maximal number of edges ofa (p ? 1)- colorable partial graph. Among others we show that a graph on n vertices with m edges has a (p?1)-colorable partial graph with at least mT_n.p/(ⁿ₂) edges, where T_n.p denotes the so called Turán number. These results are used to obtain upper bounds for special edge covering numbers of graphs. In Section 2 we prove the following theorem: If G is a simple graph and μ is the maximal cardinality of a triangle-free edge set of G, then the edges of G can be covered by μ triangles and edges. In Section 3 related questions are examined.     

Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs

The circumference of a graph is the length of its longest cycles. Results of Jackson, and Jackson and Wormald, imply that the circumference of a 3-connected cubic n-vertex graph is Ω(n^0.694), and the circumference of a 3-connected claw-free graph is Ω(n^0.121). We generalize and improve the first result by showing that every 3-edge-connected graph with m edges has an Eulerian subgraph with Ω(m^0.753) edges. We use this result together with the Ryjá?ek closure operation to improve the lower bound on the circumference of a 3-connected claw-free graph to Ω(n^0.753). Our proofs imply polynomial time algorithms for finding large Eulerian subgraphs of 3-edge-connected graphs and long cycles in 3-connected claw-free graphs.     

On extremal k-outconnected graphs

Let G be a minimally k-connected graph with n nodes and m edges. Mader proved that if n?3k-2 then m?k(n-k), and for n?3k-1 an equality is possible if, and only if, G is the complete bipartite graph K_k,n-k. Cai proved that if n?3k-2 then m?⌊(n+k)²/8⌋, and listed the cases when this bound is tight.In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.     

The clique-separator graph for chordal graphs

We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph, proper interval graph, or split graph. We also characterize proper interval graphs and split graphs in terms of the clique-separator graph. We present an algorithm that constructs the clique-separator graph of a chordal graph in O(n³) time and of an interval graph in O(n²) time, where n is the number of vertices in the graph.     

Intersection reverse sequences and geometric applications

Pinchasi and Radoi?i? [On the number of edges in geometric graphs with no self-intersecting cycle of length 4, in: J. Pach (Ed.), Towards a Theory of Geometric Graphs, Contemporary Mathematics, vol. 342, American Mathematical Society, Providence, RI, 2004] used the following observation to bound the number of edges of a topological graph without a self-crossing cycle of length 4: if we make a list of the neighbors for every vertex in such a graph and order these lists cyclically according to the order of the emanating edges, then the common elements in any two lists have reversed cyclic order. Building on their work we give an improved estimate on the size of the lists having this property. As a consequence we get that a topological graph on n vertices not containing a self-crossing C₄ has O(n^3/2logn) edges. Our result also implies that n pseudo-circles in the plane can be cut into O(n^3/2logn) pseudo-segments, which in turn implies bounds on point-curve incidences and on the complexity of a level of an arrangement of curves.     

A construction of Gray codes inducing complete graphs

A binary Gray code G(n) of length n, is a list of all 2ⁿn-bit codewords such that successive codewords differ in only one bit position. The sequence of bit positions where the single change occurs when going to the next codeword in G(n), denoted by S(n)?s₁,s₂,…,s_2ⁿ-1, is called the transition sequence of the Gray code G(n). The graph G_G(n) induced by a Gray code G(n) has vertex set {1,2,…,n} and edge set {{s_i,s_i+1}:1?i?2ⁿ-2}. If the first and the last codeword differ only in position s_2ⁿ, the code is cyclic and we extend the graph by two more edges {s_2ⁿ-1,s_2ⁿ} and {s_2ⁿ,s₁}. We solve a problem of Wilmer and Ernst [Graphs induced by Gray codes, Discrete Math. 257 (2002) 585-598] about a construction of an n-bit Gray code inducing the complete graph K_n. The technique used to solve this problem is based on a Gray code construction due to Bakos [A. Ádám, Truth Functions and the Problem of their Realization by Two-Terminal Graphs, Akadémiai Kiadó, Budapest, 1968], and which is presented in D.E. Knuth [The Art of Computer Programming, vol. 4, Addison-Wesley as part of “fascicle” 2, USA, 2005].     

Decomposition of complete graphs into (0, 2)-prisms

R. Frucht and J.Gallian (1988) proved that bipartite prisms of order 2n have an α-labeling, thus they decompose the complete graph K _6nx+1 for any positive integer x. We use a technique called the ? ⁺-labeling introduced by S. I. El-Zanati, C. Vanden Eynden, and N. Punnim (2001) to show that also some other families of 3-regular bipartite graphs of order 2n called generalized prisms decompose the complete graph K _6nx+1 for any positive integer x.     

Ramsey numbers of cubes versus cliques

The cube graph Q _n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2 ⁿ vertices. The Ramsey number r(Q _n ;K _s ) is the minimum N such that every graph of order N contains the cube graph Q _n or an independent set of order s. In 1983, Burr and Erd?s asked whether the simple lower bound r(Q _n ;K _s )≥(s?1)(2 ⁿ ?1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.