An upper bound for the path number of a graph

The path number of a graph G, denoted p(G), is the minimum number of edge-disjoint paths covering the edges of G. Lovász has proved that if G has u odd vertices and g even vertices, then p(G) ≤ 1/2 u + g - 1 ≤ n - 1, where n is the total number of vertices of G. This paper clears up an error in Lovász's proof of the above result and uses an extension of his construction to show that p(G) ≤ 1/2 u + [3/4g] ≤ [3/4n].     

On p-intersection representations

For a graph G = (V,E) and integer p, a p-intersection representation is a family F = {S_x: × E V} of subsets of a set S with the property that |S_u ∩ S_ν| ≥ p ∩ {u, ν} E E. It is conjectured in [1] that θ_p(G) ≤ θ (K_n/2,n/2) (1 + o(1)) holds for any graph with n vertices. This is known to be true for p = 1 by [4]. In [1], θ (K_n/2,n/2) ≥ (n² + (2p− 1n)n)/4p is proved for any n and p. Here, we show that this is asymptotically best possible. Further, we provide a bound on θp(G) for all graphs with bounded degree. In particular, we prove θp(G) ≤ O(n^1/p) for any graph Gwith the maximum degree bounded by a constant. Finally, we also investigate the value of θ_p for trees. Improving on an earlier result of M. Jacobson, A. Kézdy, and D. West, (The 2-intersection number of paths and bounded-degree trees, preprint), we show that θ₂(T) ≤ O(d√n) for any tree T with maximum-degree d and θ₂(T) ≤ O(n^3/4) for any tree on n vertices. We conjecture that our results can be further improved and that θ₂(T) ≤ O(d√n) as long as Δ(T) ≤ √n. If this conjecture is true, our method gives θ₂(T) ≤ O(n^3/4) for any tree T which would be the best possible. © 1996 John Wiley & Sons, Inc.     

Bounds on a generalized domination parameter

Abstract

If n is an integer, n ≥ 2 and u and v are vertices of a graph G, then u and v are said to be K_n-adjacent vertices of G if there is a subgraph of G, isomorphic to K_n , containing u and v. For n ≥ 2, a K_n- dominating set of G is a set D of vertices such that every vertex of G belongs to D or is K_n-adjacent to a vertex of D. The K_n-domination number γK_n (G) of G is the minimum cardinality among the K_n-dominating sets of vertices of G. It is shown that, for n ε {3,4}, if G is a graph of order p with no K_n-isolated vertex, then γK_n (G) ≤ p/n. We establish that this is a best possible upper bound. It is shown that the result is not true for n ≥ 5.     

UPPER BOUNDS ON THE LOWER OPEN PACKING NUMBER OF A TREE

Abstract

Let G be a graph and let v be a vertex of G. The open neigbourhood N(v) of v is the set of all vertices adjacent with v in G. An open packing of G is a set of vertices whose open neighbourhoods are pairwise disjoint. The lower open packing number of G, denoted ρ^° _L(G), is the minimum cardinality of a maximal open packing of G while the (upper) open packing number of G, denoted ρ^°(G), is the maximum cardinality among all open packings of G. It is known (see [7]) that if G is a connected graph of order n ≥3, then ρ^°(G) ≤ 2n/3 and this bound is sharp (even for trees). As a consequence of this result, we know that ρ^° _L(G) ≤ 2n/3. In this paper, we improve this bound when G is a tree. We show that if G is a tree of order n with radius 3, then ρ^° _L(G) ≤ n/2 + 2 √n-1, and this bound is sharp, while if G is a tree of order n with radius at least 4, then ρ^° _L(G) is bounded above by 2n/3—O√n).     

An extension of Vizing's theorem

Let G = (V (G), E (G)) be a simple graph of maximum degree δ ≤ D such that the graph induced by vertices of degree D is either a null graph or is empty. We give an upper bound on the number of colours needed to colour a subset S of V (G) ∪ E (G) such that no adjacent or incident elements of S receive the same colour. In particular, if S = E (G), we have the chromatic index χ′(G) ≤ D whereas if S = V (G) ∪ E (G) and for some positive integer k, we have the total chromatic number _χT(G) ≤ D + k. © 1997 John Wiley & Sons, Inc.     

The average Steiner distance of a graph

The average distance μ(G) of a graph G is the average among the distances between all pairs of vertices in G. For n ≥ 2, the average Steiner n-distance μ_n(G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, μ_n(G) ≤ μ_k(G) + μ_n+1−k(G) where 2 ≤ k ≤ n − 1. The range for the average Steiner n-distance of a connected graph G in terms of n and |V(G)| is established. Moreover, for a tree T and integer k, 2 ≤ k ≤ n − 1, it is shown that μ_n(T) ≤ (n/k)μ_k(T) and the range for μ_n(T) in terms of n and |V(T)| is established. Two efficient algorithms for finding the average Steiner n-distance of a tree are outlined. © 1996 John Wiley & Sons, Inc.     

On graphs containing a given graph as center

We examine the problem of embedding a graph H as the center of a supergraph G, and we consider what properties one can restrict G to have. Letting A(H) denote the smallest difference ∣V(G)∣ - ∣V(H)∣ over graphs G having center isomorphic to H it is demonstrated that A(H) ≤ 4 for all H, and for 0 ≤ i ≤ 4 we characterize the class of trees T with A(T) = i. for n ≥ 2 and any graph H, we demonstrate a graph G with point and edge connectivity equal to n, with chromatic number X(G) = n + X(H), and whose center is isomorphic to H. Finally, if ∣V(H)∣ ≥ 9 and k ≥ ∣V(H)∣ + 1, then for n sufficiently large (with n even when k is odd) we can construct a k-regular graph on n vertices whose center is isomorphic to H.     

Spectra of Some Interesting Combinatorial Matrices Related to Oriented Spanning Trees on a Directed Graph

The Laplacian of a directed graph G is the matrix L(G) = O(G) –, A(G) where A(G) is the adjaceney matrix of G and O(G) the diagonal matrix of vertex outdegrees. The eigenvalues of G are the eigenvalues of A(G). Given a directed graph G we construct a derived directed graph D(G) whose vertices are the oriented spanning trees of G. Using a counting argument, we describe the eigenvalues of D(G) and their multiplicities in terms of the eigenvalues of the induced subgraphs and the Laplacian matrix of G. Finally we compute the eigenvalues of D(G) for some specific directed graphs G. A recent conjecture of Propp for D(H _n ) follows, where H _n stands for the complete directed graph on n vertices without loops.     

On digraphs without antidirected cycles

Let t(n) denote the greatest number of arcs in a diagraph of orders n which does not contain any antidrected cycles. We show that [16/5(n ? 1)] ≤ t(n) ≤ 1/2 (n ? 1) for n ≥ 5. Let t_r (n) denote the corresponding quantity for r-colorable digraphs. We show that [16/5(n ? 1)] ≤ t₅(n) ≤ t₆(n) ≤ 10/3(n ? 1) for n ≥ 5 and that t₄(n) = 3(n ? 1) for n ≥ 3.     

Regularity of minimizers of semilinear elliptic problems up to dimension 4

We consider the class of semistable solutions to semilinear equations ?Δu = f(u) in a bounded smooth domain Ω of \input amssym $\Bbb R^n$ (with Ω convex in some results). This class includes all local minimizers, minimal, and extremal solutions. In dimensions n ≤ 4, we establish an a priori L^∞‐bound that holds for every positive semistable solution and every nonlinearity f. This estimate leads to the boundedness of all extremal solutions when n = 4 and Ω is convex. This result was previously known only in dimensions n ≤ 3 by a result of G. Nedev. In dimensions 5 ≤ n ≤ 9 the boundedness of all extremal solutions remains an open question. It is only known to hold in the radial case Ω = B_R by a result of A. Capella and the author. © 2010 Wiley Periodicals, Inc.     

Differential Inequalities and Starlikeness

We study some differential inequalities in the unit disc which imply starlikeness: for example if ? (z) = z + Σ^∞ _n=2 a_n (?)zⁿ is analytic in D = {z | |z| < 1} and |z(?′′(z) ? 1)| ≤ 1 ? α, z?D for some α ] [0, 1), then ? is one-to-one on D and ? (D) is a starlike domain with respect to the origin.     

On Steiner 3-wise balanced designs of order 17

We determine all S(3, κ, 17)'s which either; (i) have a block of size at least 6; or (ii) have an automorphism group order divisible by 17, 5, or 3; or (iii) contain a semi-biplane; or (iv) come from an S(3, κ, 16) which is not an S(3, 4, 16). There is an S(3, κ, 17) with |G| = n if and only if n ϵ {2^a3^b: 0 ≤ a ≤ 7,0 ≤ b ≤ 1} ∪ {18, 60, 144, 288, 320, 1920, 5760, 16320}. We also search the S(3, κ, 17)'s listed in the appendix for subdesigns S(2, κ, 17) and generate 22 nonisomorphic S(3, κ, 18)'s by adding a new point to such a subdesign. © 1997 John Wiley & Sons, Inc.     

Cycles in bipartite graphs and an application in number theory

Let G = G(A, B) be a bipartite graph with |A| = u, |B| = v, and let / be a positive integer. In this paper we prove the following result: If v ≤ u, uv ≤ n, m = |E(G)|, and m ≥ max{180/u, 20/n^{1/2(1+(1/l))},} then G contains a C_2/. © 1995 John Wiley & Sons, Inc.     

On three zero-sum Ramsey-type problems

For a graph G whose number of edges is divisible by k, let R(G,Z_k) denote the minimum integer r such that for every function f: E(K_r) ? Z_k there is a copy G¹ of G in K_r so that Σe∈E(G¹) f(e) = 0 (in Z_k). We prove that for every integer k₁ R(K_n, Z_k) ≤ n + O(k³ log k) provided n is sufficiently large as a function of k and k divides (). If, in addition, k is an odd prime-power then R(K_n, Z_k) ≤ n + 2k - 2 and this is tight if k is a prime that divides n. A related result is obtained for hypergraphs. It is further shown that for every graph G on n vertices with an even number of edges R(G,Z₂) ≤ n + 2. This estimate is sharp. © 1993 John Wiley & Sons, Inc.     

The size of graphs without nowhere-zero 4-flows

Let G be a 2-edge-connected simple graph with order n. We show that if | V(G)| ≤ 17, then either G has a nowhere-zero 4-flow, or G is contractible to the Petersen graph. We also show that for n large, if | V(G)| n ? 17/2 + 34, then either G has a nonwhere-zero 4-flow, or G can be contracted to the Petersen graph. © 1995 John Wiley & Sons, Inc.     

Exponential bounds on the number of designs with affine parameters

It is well‐known that the number of designs with the parameters of a classical design having as blocks the hyperplanes in PG(n, q) or AG(n, q), n≥3, grows exponentially. This result was extended recently [D. Jungnickel, V. D. Tonchev, Des Codes Cryptogr, published online: 23 May, 2009] to designs having the same parameters as a projective geometry design whose blocks are the d‐subspaces of PG(n, q), for any 2≤d≤n−1. In this paper, exponential lower bounds are proved on the number of non‐isomorphic designs having the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, q), for any 2≤d≤n−1, as well as resolvable designs with these parameters. An exponential lower bound is also proved for the number of non‐isomorphic resolvable 3‐designs with the same parameters as an affine geometry design whose blocks are the d‐subspaces of AG(n, 2), for any 2≤d≤n−1. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 475–487, 2010     

Induced subgraphs of prescribed size

A subgraph of a graph G is called trivial if it is either a clique or an independent set. Let q(G) denote the maximum number of vertices in a trivial subgraph of G. Motivated by an open problem of Erd?s and McKay we show that every graph G on n vertices for which q(G)≤ C log n contains an induced subgraph with exactly y edges, for every y between 0 and n^{δ (C)}. Our methods enable us also to show that under much weaker assumption, i.e., q(G) ≤ n/14, G still must contain an induced subgraph with exactly y edges, for every y between 0 and . © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 239–251, 2003     

Locally semicomplete digraphs that are complementary m-pancyclic

If A and B are two subdigraphs of D, then we denote by d_D (A, B) the distance between A and B. Let D be a 2-connected locally semicomplete digraph on n ≥ 6 vertices. If S is a minimum separating set of D and then m = max{3, d + 2} ≤ n/2 and D contains two vertex-disjoint dicycles of lengths t and n − t for every integer t satisfying m ≤ t ≤ n/2, unless D is a member of a family of locally semicomplete digraphs. This result extends those of Reid (Ann. Discrete Math. 27 (1985), 321–334) and Song (J. Combin. Theory B 57 (1993), 18–25) for tournaments, and it confirms two conjectures of Bang-Jensen (Discrete Math. 100 (1992), 243–265. © 1996 John Wiley & Sons, Inc.     

Diameters of iterated clique graphs of chordal graphs

The clique graph K(G) of a graph is the intersection graph of maximal cliques of G. The iterated clique graph Kⁿ(G) is inductively defined as K(K^n?1(G)) and K¹(G) = K(G). Let the diameter diam(G) be the greatest distance between all pairs of vertices of G. We show that diam(Kⁿ(G)) = diam(G) — n if G is a connected chordal graph and n ≤ diam(G). This generalizes a similar result for time graphs by Bruce Hedman.     

On invertible terraces for non‐abelian groups

We give several constructions for invertible terraces and invertible directed terraces. These enable us to give the first known infinite families of invertible terrraces, both directed and undirected, for non‐abelian groups. In particular, we show that all generalized dicyclic groups of orders 24k + 4 and 24k + 20 have an invertible directed terrace and that all groups of the form A × G have an invertible terrace, where A is an (possibly trivial) abelian group of odd order and G is any one of: (i) a generalized dihedral group of order 12k + 2 or 12k + 10; (ii) a generalized dicyclic group of order 24k + 4 or 24k + 20; (iii) a non‐abelian group of order n with 10 ≤ n ≤ 21; (iv) a non‐abelian binary group of order n with 24 ≤ n ≤ 42. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 437–447, 2007