Graphs having distance-n domination number half their order

For any positive integer n and any graph G a set D of vertices of G is a distance-n dominating set, if every vertex vV(G)−D has exactly distance n to at least one vertex in D. The distance-n domination number γ_=n(G) is the smallest number of vertices in any distance-n dominating set. If G is a graph of order p and each vertex in G has distance n to at least one vertex in G, then the distance-n domination number has the upper bound p/2 as Ore's upper bound on the classical domination number. In this paper, a characterization is given for graphs having distance-n domination number equal to half their order, when the diameter is greater or equal 2n−1. With this result we confirm a conjecture of Boland, Haynes, and Lawson.     

Maximum number of edges in a critically k-connected graph

A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p²/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs.     

The coordinate representation of a graph and n-universal graph of radius 1

Every graph can be represented as the intersection graph on a family of closed unit cubes in Euclidean space Eⁿ. Cube vertices have integer coordinates. The coordinate matrix, A(G)={v_nk} of a graph G is defined by the set of cube coordinates. The imbedded dimension of a graph, Bp(G), is a number of columns in matrix A(G) such that each of them has at least two distinct elements v_nk≠v_pk. We show that Bp(G)=cub(G) for some graphs, and Bp(G)n−2 for any graph G on n vertices. The coordinate matrix uses to obtain the graph U of radius 1 with 3ⁿ⁻² vertices that contains as an induced subgraph a copy of any graph on n vertices.     

On ringeisen's isolation game

We develop the theory of the Isolation Game on a graph G, in which two players alternately “switch” at successive vertices v not previously switched. The switching operation deletes all edges incident with v, and creates new edges between v and those vertices not previously adjacent to it. The game is won when a vertex is first isolated. Among other results, we show that n-vertex forced wins exist for all n, and that length-p forced wins exist for all p. We give generic examples of forced wins which (against best defense) can be won only very late in the game. We also prove several large classes of graphs to be unwinnable, and give a complexity results for a problem closely related to the identification of drawing strategies in I_n(G).     

Primitive graphs with given exponents and minimum number of edges

A graph G = (V, E) on n vertices is primitive if there is a positive integer k such that for each pair of vertices u, v of G, there is a walk of length k from u to v. The minimum value of such an integer, k, is the exponent, exp(G), of G. In this paper, we find the minimum number, h(n, k), of edges of a simple graph G on n vertices with exponent k, and we characterize all graphs which have h(n, k) edges when k is 3 or even.     

Profile minimization on triangulated triangles

Given graph G=(V,E) on n vertices, the profile minimization problem is to find a one-to-one function f:V→{1,2,…,n} such that ∑_vV(G){f(v)−min_xN[v] f(x)} is as small as possible, where N[v]={v}{x: x is adjacent to v} is the closed neighborhood of v in G. The trangulated triangle T_l is the graph whose vertices are the triples of non-negative integers summing to l, with an edge connecting two triples if they agree in one coordinate and differ by 1 in the other two coordinates. This paper provides a polynomial time algorithm to solve the profile minimization problem for trangulated triangles T_l with side-length l.     

The order-interval hypergraph of a finite poset and the König property

We study the hypergraph H(P) whose vertices are the points of a finite poset and whose edges are the maximal intervals in P (i.e. sets of the form I = {{v ε P: p ν q}}, p minimal, q maximal). We mention resp. show that the problems of the determination of the independence number , the point covering number τ, the matching number v and the edge covering number p are NP-complete. For interval orders we describe polynomial algorithms and prove the König property (v = τ) and the dual König property (a = p). Finally we show that the (dual) König property is preserved by product.     

Decomposition of some planar graphs into trees

We prove that each simple planar graph G whose all faces are quadrilaterals can be decomposed into two disjoint trees T_r and T_b such that V(T_r) = V(G − u) and V(T_b) = V(G − v) for any two non-adjacent vertices u and v of G.     

On embedding an outer-planar graph in a point set

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog³n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n²) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.     

Multicolor routing in the undirected hypercube

An undirected routing problem is a pair (G,R) where G is an undirected graph and R is an undirected multigraph such that V(G)=V(R). A solution to an undirected routing problem (G,R) is a collection P of undirected paths of G (possibly containing multiple occurrences of the same path) such that edges of R are in one-to-one correspondence with the paths of P, with the path corresponding to edge {u,v} connecting u and v. We say that a collection of paths P is k-colorable if each path of P can be colored by one of the k colors so that the paths of the same color are edge-disjoint (each edge of G appears at most once in the paths of each single color). In the circuit-switched routing context, and in optical network applications in particular, it is desirable to find a solution to a routing problem that is colorable with as few colors as possible. Let Q_n denote the n-dimensional hypercube, for arbitrary n1. We show that a routing problem (Q_n,R) always admits a 4d-colorable solution where d is the maximum vertex degree of R. This improves over the 16d/2-color result which is implicit in the previous work of Aumann and Rabani [SODA95, pp. 567–576]. Since, for any positive d, there is a multigraph R of degree d such that any solution to (Q_n,R) requires at least d colors, our result is tight up to a factor of four. In fact, when d=1, it is tight up to a factor of two, since there is a graph of degree one (the antipodal matching) that requires two colors.     

Solvable block transitive automorphism groups of 2−(v,5,1) designs

Let G be a solvable block transitive automorphism group of a 2−(v,5,1) design and suppose that G is not flag transitive. We will prove that

(1) if G is point imprimitive, then v=21, and GZ₂₁:Z₆;

(2) if G is point primitive, then GAΓL(1,v) and v=p^a, where p is a prime number with p≡21 (mod 40), and a an odd integer.

     

Hamiltonian cycles in n-factor-critical graphs

A graph G is said to be n-factor-critical if G−S has a 1-factor for any SV(G) with |S|=n. In this paper, we prove that if G is a 2-connected n-factor-critical graph of order p with , then G is hamiltonian with some exceptions. To extend this theorem, we define a (k,n)-factor-critical graph to be a graph G such that G−S has a k-factor for any SV(G) with |S|=n. We conjecture that if G is a 2-connected (k,n)-factor-critical graph of order p with , then G is hamiltonian with some exceptions. In this paper, we characterize all such graphs that satisfy the assumption, but are not 1-tough. Using this, we verify the conjecture for k2.     

Magic Labeling of Disjoint Union Graphs

Let G be a graph with vertex set V (G), edge set E(G) and maximum degree Δ respectively. G is called degree-magic if it admits a labelling of the edges by integers {1, 2, …,|E(G)|} such that for any vertex v the sum of the labels of the edges incident with v is equal to (1+|E(G)|)/2·d(v), where d(v) is the degree of v. Let f be a proper edge coloring of G such that for each vertex v ∈ V (G),|{e:e ∈ E_v, f(e) ≤ Δ/2}|=|{e:e ∈ E_v, f(e) > Δ/2}|, and such an f is called a balanced edge coloring of G. In this paper, we show that if G is a supermagic even graph with a balanced edge coloring and m ≥ 1, then (2m + 1)G is a supermagic graph. If G is a d-magic even graph with a balanced edge coloring and n ≥ 2, then nG is a d-magic graph. Results in this paper generalise some known results.     

Bandwidth of the composition of two graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(x)−f(y)| : xyE(G)} taken over all proper numberings f of G. The composition of two graphs G and H, written as G[H], is the graph with vertex set V(G)×V(H) and with (u₁,v₁) is adjacent to (u₂,v₂) if either u₁ is adjacent to u₂ in G or u₁=u₂ and v₁ is adjacent to v₂ in H. In this paper, we investigate the bandwidth of the composition of two graphs. Let G be a connected graph. We denote the diameter of G by D(G). For two distinct vertices x,yV(G), we define w_G(x,y) as the maximum number of internally vertex-disjoint (x,y)-paths whose lengths are the distance between x and y. We define w(G) as the minimum of w_G(x,y) over all pairs of vertices x,y of G with the distance between x and y is equal to D(G). Let G be a non-complete connected graph and let H be any graph. Among other results, we prove that if |V(G)|=B(G)D(G)−w(G)+2, then B(G[H])=(B(G)+1)|V(H)|−1. Moreover, we show that this result determines the bandwidth of the composition of some classes of graphs composed with any graph.     

Choosability of planar graphs

A graph G = G(V, E) with lists L(v), associated with its vertices v V, is called L-list colourable if there is a proper vertex colouring of G in which the colour assigned to a vertex v is chosen from L(v). We say G is k-choosable if there is at least one L-list colouring for every possible list assignment L with L(v) = k v V(G).

Now, let an arbitrary vertex v of G be coloured with an arbitrary colour f of L(v). We investigate whether the colouring of v can be continued to an L-list colouring of the whole graph. G is called free k-choosable if such an L-list colouring exists for every list assignment L (L(v) = k v V(G)), every vertex v and every colour f L(v). We prove the equivalence of the well-known conjecture of Erd s et al. (1979): “Every planar graph is 5-choosable” with the following conjecture: “Every planar graph is free 5-choosable”.     

Large eigenvalues of the laplacian

Let G be a simple graph on n vertices and let L=L(G) be the Laplacian matrix of G corresponding to some ordering of the vertices. It is known that λ≤n for any eigenvalue λ of L. In this note we characterize when n is an eigenvalue of L with multiplicity m.     

Ramsey linear families and generalized subdivided graphs

The following results are obtained. (i) Let p, d, and k be fixed positive integers, and let G be a graph whose vertex set can be partitioned into parts V₁, V₂,…, V_a such that for each i at most d vertices in V₁ … V_i have neighbors in V_i+1 and r(K_k, V_i) p | V(G) |, where V_i denotes the subgraph of G induced by V_i. Then there exists a number c depending only on p, d, and k such that r(K_k, G)c | V(G) |. (ii) Let d be a positive integer and let G be a graph in which there is an independent set I V(G) such that each component of G−I has at most d vertices and at most two neighbors in I. Then r(G,G)c | V(G) |, where c is a number depending only on d. As a special case, r(G, G) 6 | V(G) | for a graph G in which all vertices of degree at least three are independent. The constant 6 cannot be replaced by one less than 4.     

The integrity of a cubic graph

Integrity, a measure of network reliability, is defined as

where G is a graph with vertex set V and m(G−S) denotes the order of the largest component of G−S. We prove an upper bound of the following form on the integrity of any cubic graph with n vertices:

Moreover, there exist an infinite family of connected cubic graphs whose integrity satisfies a linear lower bound I(G)>βn for some constant β. We provide a value for β, but it is likely not best possible. To prove the upper bound we first solve the following extremal problem. What is the least number of vertices in a cubic graph whose removal results in an acyclic graph? The solution (with a few minor exceptions) is that n/3 vertices suffice and this is best possible.     

Sum coloring and interval graphs: a tight upper bound for the minimum number of colors

The SUM COLORING problem consists of assigning a color c(v_i)Z⁺ to each vertex v_iV of a graph G=(V,E) so that adjacent nodes have different colors and the sum of the c(v_i)'s over all vertices v_iV is minimized. In this note we prove that the number of colors required to attain a minimum valued sum on arbitrary interval graphs does not exceed min{n;2χ(G)−1}. Examples from the papers [Discrete Math. 174 (1999) 125; Algorithmica 23 (1999) 109] show that the bound is tight.     

Weighted domination in triangle-free graphs

A weighted graph (G,w) is a graph G together with a positive weight-function on its vertex set w : V(G)→R^>0. The weighted domination number γ_w(G) of (G,w) is the minimum weight w(D)=∑_vDw(v) of a set DV(G) such that every vertex xV(D)−D has a neighbor in D. If ∑_vV(G)w(v)=|V(G)|, then we speak of a normed weighted graph. Recently, we proved that

for normed weighted bipartite graphs (G,w) of order n such that neither G nor the complement has isolated vertices. In this paper we will extend these Nordhaus–Gaddum-type results to triangle-free graphs.