Super connectivity of Kronecker products of graphs

Let G₁ and G₂ be two connected graphs. The Kronecker product G₁×G₂ has vertex set V(G₁×G₂)=V(G₁)×V(G₂) and the edge set . In this paper, we show that if G is a bipartite graph with κ(G)=δ(G), then G×Kn(n?3) is super-κ.     

Ranking numbers of graphs

Given a graph G, a vertex ranking (or simply, ranking) of G is a mapping f from V(G) to the set of all positive integers, such that for any path between two distinct vertices u and v with f(u)=f(v), there is a vertex w in the path with f(w)>f(u). If f is a ranking of G, the ranking number of G under f, denoted γf(G), is defined by , and the ranking number of G, denoted γ(G), is defined by . The vertex ranking problem is to determine the ranking number γ(G) of a given graph G. This problem is a natural model for the manufacturing scheduling problem. We study the ranking numbers of graphs in this paper. We consider the relation between the ranking numbers and the minimal cut sets, and the relation between the ranking numbers and the independent sets. From this, we obtain the ranking numbers of the powers of paths and the powers of cycles, the Cartesian product of P₂ with Pn or Cn, and the caterpilars. And we also find the vertex ranking numbers of the composition of two graphs in this paper.     

On edge connectivity of direct products of graphs

Let λ(G) be the edge connectivity of G. The direct product of graphs G and H is the graph with vertex set V(G×H)=V(G)×V(H), where two vertices (u₁,v₁) and (u₂,v₂) are adjacent in G×H if u₁u₂∈E(G) and v₁v₂∈E(H). We prove that λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(G)} for every nontrivial graph G and n?3. We also prove that for almost every pair of graphs G and H with n vertices and edge probability p, G×H is k-connected, where k=O(²(n/logn)).     

Signed and minus clique-transversal functions on graphs

A minus (respectively, signed) clique-transversal function of a graph G=(V,E) is a function (respectively, {−1,1}) such that _∑u∈Cf(u)?1 for every maximal clique C of G. The weight of a minus (respectively, signed) clique-transversal function of G is f(V)=_∑v∈Vf(v). The minus (respectively, signed) clique-transversal problem is to find a minus (respectively, signed) clique-transversal function of G of minimum weight. In this paper, we present a unified approach to these two problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. We also prove that the signed clique-transversal problem is NP-complete for chordal graphs and planar graphs.     

Weighted Coloring: further complexity and approximability results

Given a vertex-weighted graph G=(V,E;w), w(v)?0 for any v∈V, we consider a weighted version of the coloring problem which consists in finding a partition S=(S₁,…,Sk) of the vertex set of G into stable sets and minimizing where the weight of S is defined as . In this paper, we continue the investigation of the complexity and the approximability of this problem by answering some of the questions raised by Guan and Zhu [D.J. Guan, X. Zhu, A coloring problem for weighted graphs, Inform. Process. Lett. 61 (2) (1997) 77-81].     

Enhanced algorithms for Local Search

Let G=(V,E) be a finite graph, and be any function. The Local Search problem consists in finding a local minimum of the function f on G, that is a vertex v such that f(v) is not larger than the value of f on the neighbors of v in G. In this note, we first prove a separation theorem slightly stronger than the one of Gilbert, Hutchinson and Tarjan for graphs of constant genus. This result allows us to enhance a previously known deterministic algorithm for Local Search with query complexity , so that we obtain a deterministic query complexity of , where n is the size of G, d is its maximum degree, and g is its genus. We also give a quantum version of our algorithm, whose query complexity is of . Our deterministic and quantum algorithms have query complexities respectively smaller than the algorithm Randomized Steepest Descent of Aldous and Quantum Steepest Descent of Aaronson for large classes of graphs, including graphs of bounded genus and planar graphs.     

2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs

An important optimization problem in the design of cellular networks is to assign sets of frequencies to transmitters to avoid unacceptable interference. A cellular network is generally modeled as a subgraph of the infinite triangular lattice. The distributed frequency assignment problem can be abstracted as a multicoloring problem on a weighted hexagonal graph, where the weight vector represents the number of calls to be assigned at vertices. In this paper we present a 2-local distributed algorithm for multicoloring triangle-free hexagonal graphs using only the local clique numbers ω₁(v) and ω₂(v) at each vertex v of the given hexagonal graph, which can be computed from local information available at the vertex. We prove that the algorithm uses no more than colors for any triangle-free hexagonal graph G, without explicitly computing the global clique number ω(G). Hence the competitive ratio of the algorithm is 5/4.     

On domination number of Cartesian product of directed cycles

Let γ(G) denote the domination number of a digraph G and let Cm□Cn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In this paper, we determine the exact values: γ(C₂□Cn)=n; γ(C₃□Cn)=n if , otherwise, γ(C₃□Cn)=n+1; if , otherwise, .     

The Pair Completion algorithm for the Homogeneous Set Sandwich Problem

A homogeneous set is a non-trivial module of a graph, i.e., a non-empty, non-unitary, proper vertex subset such that all its elements present the same outer neighborhood. Given two graphs G₁(V,E₁) and G₂(V,E₂), the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a graph GS(V,ES), E₁⊆ES⊆E₂, which has a homogeneous set. This paper presents an algorithm that uses the concept of bias graph [S. Tang, F. Yeh, Y. Wang, An efficient algorithm for solving the homogeneous set sandwich problem, Inform. Process. Lett. 77 (2001) 17-22] to solve the problem in time, thus outperforming the other known HSSP deterministic algorithms for inputs where .     

Maximum induced subgraph of a recursive circulant

The recursive circulant RC(n²,4) enjoys several attractive topological properties. Let max_?G(m) denote the maximum number of edges in a subgraph of graph G induced by m nodes. In this paper, we show that , where p₀>p₁>?>pr are nonnegative integers defined by . We then apply this formula to find the bisection width of RC(n²,4). The conclusion shows that, as n-dimensional cube, RC(n²,4) enjoys a linear bisection width.     

Strong product of factor-critical graphs

Strong product G ₁? G ₂ of two graphs G ₁ and G ₂ has a vertex set V(G ₁)×V(G ₂) and two vertices (u ₁, v ₁) and (u ₂, v ₂) are adjacent whenever u ₁=u ₂ and v ₁ is adjacent to v ₂ or u ₁ is adjacent to u ₂ and v ₁=v ₂, or u ₁ is adjacent to u ₂ and v ₁ is adjacent to v ₂. We investigate the factor-criticality of G ₁? G ₂ and obtain the following. Let G ₁ and G ₂ be connected m-factor-critical and n-factor-critical graphs, respectively. Then i. if m? 0, n=0, |V(G ₁)|? 2m+2 and |V(G ₂)|? 4, then G ₁? G ₂ is (2m+2)-factor-critical;

ii. if n=1, |V(G ₁)|? 2m+3 and either m? 3 or |V(G ₂)|? 5, then G ₁? G ₂ is (2m+4??)-factor-critical, where ?=0 if m is even, otherwise ?=1;

iii. if m+2 ? |V(G ₁)|? 2m+2, or n+2? |V(G ₂)|? 2n+2, then G ₁? G ₂ is mn-factor-critical;

iv. if |V(G ₁)|? 2m+3 and |V(G ₂)|? 2n+3, then G ₁? G ₂ is (mn?min{[3m/2]₂, [3n/2]₂})-factor-critical.

     

Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes

An adjacent vertex-distinguishing edge coloring of a simple graph G is a proper edge coloring of G such that incident edge sets of any two adjacent vertices are assigned different sets of colors. A total coloring of a graph G is a coloring of both the edges and the vertices. A total coloring is proper if no two adjacent or incident elements receive the same color. An adjacent vertex-distinguishing total coloring h of a simple graph G=(V,E) is a proper total coloring of G such that H(u)≠H(v) for any two adjacent vertices u and v, where H(u)={h(wu)|wu∈E(G)}∪{h(u)} and H(v)={h(xv)|xv∈E(G)}∪{h(v)}. The minimum number of colors required for an adjacent vertex-distinguishing edge coloring (resp. an adjacent vertex-distinguishing total coloring) of G is called the adjacent vertex-distinguishing edge chromatic number (resp. adjacent vertex-distinguishing total chromatic number) of G and denoted by (resp. χat(G)). In this paper, we consider the adjacent vertex-distinguishing edge chromatic number and adjacent vertex-distinguishing total chromatic number of the hypercube Qn, prove that for n?3 and χat(Qn)=Δ(Qn)+2 for n?2.     

Note on the connectivity of line graphs

Let G be a connected graph with vertex set V(G), edge set E(G), vertex-connectivity κ(G) and edge-connectivity λ(G).A subset S of E(G) is called a restricted edge-cut if G−S is disconnected and each component contains at least two vertices. The restricted edge-connectivity λ₂(G) is the minimum cardinality over all restricted edge-cuts. Clearly λ₂(G)?λ(G)?κ(G).In 1969, Chartrand and Stewart have shown that

     

Conditional fault hamiltonian connectivity of the complete graph

A path in G is a hamiltonian path if it contains all vertices of G. A graph G is hamiltonian connected if there exists a hamiltonian path between any two distinct vertices of G. The degree of a vertex u in G is the number of vertices of G adjacent to u. We denote by δ(G) the minimum degree of vertices of G. A graph G is conditional k edge-fault tolerant hamiltonian connected if G−F is hamiltonian connected for every F⊂E(G) with |F|?k and δ(G−F)?3. The conditional edge-fault tolerant hamiltonian connectivity is defined as the maximum integer k such that G is k edge-fault tolerant conditional hamiltonian connected if G is hamiltonian connected and is undefined otherwise. Let n?4. We use Kn to denote the complete graph with n vertices. In this paper, we show that for n∉{4,5,8,10}, , , , and .     

The complexity of changing colourings with bounded maximum degree

Let G be a graph, x,y∈V(G), and ?:V(G)→[k] a k-colouring of G such that ?(x)=?(y). If then the following question is NP-complete: Does there exist a k-colouring ?^′ of G such that ?^′(x)≠?^′(y)? Conversely, if then the problem is polynomial time.     

A spectral lower bound for the treewidth of a graph and its consequences

We give a lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. We use this lower bound to show that the treewidth of a d-dimensional hypercube is at least ⌊3·2^d/(2(d+4))⌋−1. The currently known upper bound is . We generalize this result to Hamming graphs. We also observe that every graph G on n vertices, with maximum degree Δ

(1)

contains an induced cycle (chordless cycle) of length at least 1+log_Δ(μn/8) (provided G is not acyclic),

(2)

has a clique minor K_h for some ,

where μ is the second smallest eigenvalue of the Laplacian matrix of G.