36178651
The vertex linear arboricity of distance graphs
A distance graph is a graph G(R,D) with the set of all points of the real line as vertex set and two vertices u,[email protected]?R are adjacent if and only if |u-v|@?D where the distance set D is a subset of the positive real numbers. Here, the vertex linear arboricity of G(R,D) is determined when D is an interval between 1 and @d. In particular, the vertex linear arboricity of integer distance graphs G(D) is discussed, too.
42869793
Edge-coloring critical graphs with high degree
It is proved here that any edge-coloring critical graph of order n and maximum degree Δ ≥ 8 has the size at least 3(n + Δ - 8). It generalizes a result of Hugh Hind and Yue Zhao.
1502406
Total Coloring of Series-Parallel Graphs
45978330
Two sufficient conditions for a graph to be type 1
15322039
Tree coloring of distance graphs with a real interval set
Let RR be the set of real numbers and DD be a subset of the positive real numbers. The distance graph  G(R,D)G(R,D) is a graph with the vertex set RR and two vertices xx and yy are adjacent if and only if |x−y|∈D|x−y|∈D. In this work, the vertex arboricity (i.e., the minimum number of subsets into which the vertex set V(G)V(G) can be partitioned so that each subset induces an acyclic subgraph) of G(R,D)G(R,D) is determined for DD being an interval between 1 and δδ.
32836256
Minimum average distance of strong orientations of graphs
The average distance of a graph (strong digraph) G, denoted by µ(G) is the average, among the distances between all pairs (ordered pairs) of vertices of G. If G is a 2-edge-connected graph, then µ→min(G) is the minimum average distance taken over all strong orientations of G. A lower bound for µ→min(G) in terms of the order, size, girth and average distance of G is established and shown to be sharp for several complete multipartite graphs. It is shown that there is no upper bound for µ→min(G) in terms of µ(G). However, if every edge of G lies on 3-cycle, then it is shown that µ→min(G) ≤ 7/4 µ(G). This bound is improved for maximal planar graphs to 5/3 µ(G) and even further to 3/2 µ(G) for eulerian maximal planar graphs and for outerplanar graphs with the property that every edge lies on 3-cycle. In the last case the bound is shown to be sharp.
18305448
Searching for Sorted Sequences of Kings in Tournaments
A tournament Tn is an orientation of a complete graph on n vertices. A king in a tournament is a vertex from which every other vertex is reachable by a path of length at most 2. A sorted sequence of kings in a tournament Tn is an ordered list of its vertices u1, u2, . . ., un such that ui dominates $u_{i+1}$ ($u_i \rightarrow u_{i+1}$) and $u_i$ is a king in the subtournament induced by $\{u_j: i \le j \le n\}$ for each i=1,2, . . .,n-1. In particular, if Tn is transitive, searching for a sorted sequence of kings in Tn is equivalent to sorting a set of n numbers. In this paper, we try to find a sorted sequence of kings in a general tournament by asking the following type of binary question: "What is the orientation of the edge between two specified vertices u, v?" The cost for finding a sorted sequence of kings is the minimum number of binary questions asked in order to guarantee the finding of a sorted sequence of kings. Using an adversary argument proposed in this paper, we show that the cost for finding a sorted sequence of kings in Tn is $\Theta(n^{3/2})$ in the worst case, thus settling the order of magnitude of this question. We also show that the cost for finding a king in Tn is $\Omega(n^{4/3})$ and O(n3/2) in the worst case. Finally, we show a connection between a sorted sequence of kings and a median order in a tournament.
6174033
Reliable broadcasting in wormhole-routed hypercube-connected networks using local safety information
This paper presents a method to cope with reliable broadcasting in faulty hypercubes using local safety information. A new definition, broadcast subcube, is introduced, with which various techniques are proposed to improve performance of the broadcast algorithm. Local safety information is well used in the fault-tolerant broadcast algorithm by considering only safety of the broadcast subcube. An unsafe hypercube can be split into a set of maximal safe subcubes. If these maximal safe subcubes meet certain requirements (listed in this paper), then broadcasting can still be done successfully and, in some cases, optimal broadcast is still possible. The sufficient condition for optimal broadcast of a message is presented in an unsafe hypercube. Extensive simulation results show that the proposed method outperforms previous methods, in all cases.
204989501
On clique partitions of split graphs
Abstract Split graphs are graphs formed by taking a complete graph and an empty graph disjoint from it and some or all of the possible edges joining the two. We prove that the problem of deciding the clique partition number is NP-complete, even when restricted to the class of split graphs.
42844888
Dimension-Exchange-Based Load Balancing on Injured Hypercubes
We study a global load balancing scheme on hypercubes with faulty links based on the dimension exchange scheme, where each node exchanges workloads with its neighbors along selected dimensions in such a way that their loads become equal. An algorithm that can tolerate n-1 faulty links is first presented and it can be extended to connected hypercubes with up to 2n - 3 faulty links. Comparisons between the proposed scheme with the conventional dimension-exchange-based scheme are also presented. Simulation results show that very little overhead is introduced in our scheme.
374914
On Cost-Optimal Merge of Two Intransitive Sorted Sequences
The problem of merging two intransitive sorted sequences (that is, to generate a sorted total order without the transitive property) is considered. A cost-optimal parallel merging algorithm is proposed under the EREW PRAM model. This algorithm has a run time of O(log2 n) using O(n/log2 n) processors. The cost-optimal merge in the strong sense is still an open problem.