Some results on characterizing the edges of connected graphs with a given domination number

A dominating set for a graph G = (V, E) is a subset of vertices V′ V such that for all v ε V − V′ there exists some u ε V′ for which {v, u} ε E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let m₁ (G, D) denote the number of edges that have neither endpoint in D, and let m₂ (G, D) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair (m₁ (G, D), m₂ (G, D)) can attain for connected graphs having a given domination number.     

The chromatic difference sequence of the Cartesian product of graphs

The chromatic difference sequence cds(G) of a graph G with chromatic number n is defined by cds(G) = (a(1), a(2),…, a(n)) if the sum of a(1), a(2),…, a(t) is the maximum number of vertices in an induced t-colorable subgraph of G for t = 1, 2,…, n. The Cartesian product of two graphs G and H, denoted by G□H, has the vertex set V(G□H = V(G) x V(H) and its edge set is given by (x₁, y₁)(x₂, y₂) ε E(G□H) if either x₁ = x₂ and y₁ y₂ ε E(H) or y₁ = y₂ and x₁x₂ ε E(G).

We obtained four main results: the cds of the product of bipartite graphs, the cds of the product of graphs with cds being nondrop flat and first-drop flat, the non-increasing theorem for powers of graphs and cds of powers of circulant graphs.     

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.     

On neighborhood condition for graphs to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1a<b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G)(k−1)a, n(a+b)(k(a+b)−2)/b, and |N_G(x₁)N_G(x₂)N_G(x_k)|an/(a+b) for any independent subset {x₁,x₂,…,x_k} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense.     

On the planarity of jump graphs

For a graph G of size m1 and edge-induced subgraphs F and H of size k (1km), the subgraph H is said to be obtained from F by an edge jump if there exist four distinct vertices u,v,w, and x in G such that uvE(F), wxE(G)−E(F), and H=F−uv+wx. The minimum number of edge jumps required to transform F into H is the k-jump distance from F to H. For a graph G of size m1 and an integer k with 1km, the k-jump graph J_k(G) is that graph whose vertices correspond to the edge-induced subgraphs of size k of G and where two vertices of J_k(G) are adjacent if and only if the k-jump distance between the corresponding subgraphs is 1. All connected graphs G for which J₂(G) is planar are determined.     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

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.     

Partition of a directed bipartite graph into two directed cycles

Let D = (V₁, V₂; A) be a directed bipartite graph with |V₁| = |V₂| = n 2. Suppose that d_D(x) + d_D(y) 3n + 1 for all x ε V₁ and y ε V₂. Then D contains two vertex-disjoint directed cycles of lengths 2n₁ and 2n₂, respectively, for any positive integer partition n = n₁ + n₂. Moreover, the condition is sharp for even n and nearly sharp for odd n.     

k-Subdomination in graphs

For a positive integer k, a k-subdominating function of a graph G=(V,E) is a function f : V→{−1,1} such that ∑_uNG[v]f(u)1 for at least k vertices v of G. The k-subdomination number of G, denoted by γ_ks(G), is the minimum of ∑_vVf(v) taken over all k-subdominating functions f of G. In this article, we prove a conjecture for k-subdomination on trees proposed by Cockayne and Mynhardt. We also give a lower bound for γ_ks(G) in terms of the degree sequence of G. This generalizes some known results on the k-subdomination number γ_ks(G), the signed domination number γ_s(G) and the majority domination number γ_maj(G).     

Bounds on the number of isolates in sum graph labeling

A simple undirected graph H is called a sum graph if there is a labeling L of the vertices of H into distinct positive integers such that any two vertices u and v of H are adjacent if and only if there is a vertex w with label L(w)=L(u)+L(v). The sum number σ(G) of a graph G=(V,E) is the least integer r such that the graph H consisting of G and r isolated vertices is a sum graph. It is clear that σ(G)|E|. In this paper, we discuss general upper and lower bounds on the sum number. In particular, we prove that, over all graphs G=(V,E) with fixed |V|3 and |E|, the average of σ(G) is at least

Full-size image

. In other words, for most graphs, σ(G)Ω(|E|).     

On the existence of kernels and h-kernels in directed graphs

A directed graph D with vertex set V is called cyclically h-partite (h2) provided one can partition V=V₀+V₁++V_h−1 so that if (u, υ) is an arc of D then uεV_i, and υεV_i+1 (notation mod h). In this communication we obtain a characterization of cyclically h-partite strongly connected digraphs. As a consequence we obtain a sufficient condition for a digraph to have a h-kernel.     

Inverse geophysical problems for some noncompactly supported inhomogeneities

Let[²+k²n(x₁,x₃)]u(x₁,x₂,x₃)=−δ(x₁,y₁δ(x₂,y₂)δ(x₃,y₃) in R³₊. Assume that u(x₁,x₂,x₃=0,y₁,y₂=0,y₃=0,k) is measured at the plane P {x:x₃=0} for all positions of the source on the line y = (y₁,y₂ = 0,y₃ = 0), -∞ < y₁ < ∞, and receiver on the plane(x₁,x₂,x₃ − <x₁,x₂ < ∞, and for low-frequencies 0 < k <k₀, k₀ > 0 is an arbitrary small wave number. Assume thatn(x₁,x₃) is an arbitrary bounded piecewise-continuous function. The basic result is: the above low-frequency surface data determinen(x₁,x₃)uniquely.     

路的字典积的邻和可区别边染色

图G的正常[k]-边染色σ是指颜色集合为[k]={1,2,…,k}的G的一个正常边染色.用w_σ（x）表示顶点x关联边的颜色之和,即w_σ（x）=∑_e∋x σ（e）,并称w_σ（x）关于σ的权.图G的k-邻和可区别边染色是指相邻顶点具有不同权的正常[k]-边染色,最小的k值称为G的邻和可区别边色数,记为χ'_∑（G）.现得到了路P_n与简单连通图H的字典积P_n[H]的邻和可区别边色数的精确值,其中H分别为正则第一类图、路、完全图的补图.     

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.     

Neighborhood unions and cyclability of graphs

A graph G is said to be cyclable if for each orientation of G, there exists a set S of vertices such that reversing all the arcs of with one end in S results in a hamiltonian digraph. Let G be a 3-connected graph of order n36. In this paper, we show that if for any three independent vertices x₁, x₂ and x₃, |N(x₁)N(x₂)|+|N(x₂)N(x₃)|+|N(x₃)N(x₁)|2n+1, then G is cyclable.     

Multiple positive solutions for one-dimensional p-Laplacian boundary value problems

By means of the Leggett-Williams fixed-point theorem, criteria are developed for the existence of at least three positive solutions to the one-dimensional p-Laplacian boundary value problem, ((y′))′ + g(t)f(t,y) = 0, y(0) - B₀(y′(0)) = 0, y(1) + B₁(y′(1)) = 0, where (v) |v|^p−2v, p > 1.     

Subgraph distances in graphs defined by edge transfers

For two edge-induced subgraphs F and H of the same size in a graph G, the subgraph H can be obtained from F by an edge jump if there exist four distinct vertices u, v, w, and x in G such that uv ε E(F), wx ε E(G) - E(F), and H = F - uv + wx. The subgraph F is j-transformed into H if H can be obtained from F by a sequence of edge jumps. Necessary and sufficient conditions are presented for a graph G to have the property that every edge-induced subgraph of a fixed size in G can be j-transformed into every other edge-induced subgraph of that size. The minimum number of edge jumps required to transform one subgraph into another is called the jump distance. This distance is a metric and can be modeled by a graph. The jump graph J(G) of a graph G is defined as that graph whose vertices are the edges of G and where two vertices of J(G) are adjacent if and only if the corresponding edges of G are independent. For a given graph G, we consider the sequence {{J^k(G)}} of iterated jump graphs and classify each graph as having a convergent, divergent, or terminating sequence.     

On-line algorithms for ordered sets and comparability graphs

We discuss several results concerning on-line algorithms for ordered sets and comparability graphs. The main new result is on the problem of on-line transitive orientation. We view on-line transitive orientation of a comparability graph G as a two-person game. In the ith round of play, 1 i | V(G)|, player A names a graph G_i such that G_i is isomorphic to a subgraph of G, |V(G_i)| = i, and G_i−1 is an induced subgraph of G_i if i> 1. Player B must respond with a transitive orientation of G_i which extends the transitive orientation given to G_i−1 in the previous round of play. Player A wins if and only if player B fails to give a transitive orientation to G_i for some i, 1 i |V(G)|. Our main result shows that player A has at most three winning moves. We also discuss applications to on-line clique covering of comparability graphs, and we mention some open problems.     

On the minor-minimal 2-connected graphs having a fixed minor

Let H be a graph with κ₁ components and κ₂ blocks, and let G be a minor-minimal 2-connected graph having H as a minor. This paper proves that |E(G)|−|E(H)|(κ₁−1)+β(κ₂−1) for all (,β) such that +β5,2+5β20, and β3. Moreover, if one of the last three inequalities fails, then there are graphs G and H for which the first inequality fails.     

Bipartite double cover and perfect 2-matching covered graph with its algorithm

Let B(G) denote the bipartite double cover of a non-bipartite graph G with v≥2 vertices and ? edges. We prove that G is a perfect 2-matching covered graph if and only if B(G) is a 1-extendable graph. Furthermore, we prove that B(G) is a minimally 1-extendable graph if and only if G is a minimally perfect 2-matching covered graph and for each e = xy ∈ E(G), there is an independent set S in G such that |Γ_G(S)| = |S| + 1, x ∈S and |Γ_G-xy(S) | = |S|. Then, we construct a digraph D from B(G) or G and show that D is a strongly connected digraph if and only if G is a perfect 2-matching covered graph. So we design an algorithm in O(v?) time that determines whether G is a perfect 2-matching covered graph or not.