The 2-dimensional global rigidity has been shown to be equivalent to 3-connectedness and redundant rigidity by a combination of two results due to Jackson and Jordán, and Connelly, respectively. By the characterization, a theorem of Lovász and Yemini implies that every 6-connected graph is redundantly rigid and thus globally rigid. The 6-connectedness is best possible, since there exist infinitely many 5-connected nonrigid graphs. Jackson, Servatius, and Servatius used the idea of “essential connectivity” and proved that every 4-connected “essentially 6-connected” graph is redundantly rigid and thus global rigid. Since 3-connectedness is a necessary condition of global rigidity, it is interesting to study 3-connected graphs for redundant rigidity and thus global rigidity. We utilize a different “essential connectivity” and prove that every 3-connected essentially 9-connected graph is redundantly rigid and thus globally rigid. The essential 9-connectedness is best possible. Under this essential connectivity, we also prove that every 4-connected essentially 6-connected graph is redundantly rigid and thus globally rigid. Our proofs are based on discharging arguments.

For a given graph $H$, a graph $G$ is H-linked if, for every injection $\varphi: V(H) \to V(G)$, the graph $G$ contains a subdivision of $H$ with $\varphi(v)$ corresponding to $v$ for each $v\in V(H)$. Let $f(H)$ be the minimum integer $k$ such that every $k$-connected graph is $H$-linked. Among connected simple graphs $H$ with at least four vertices, the exact value $f(H)$ is only known when $H$ is a star, or a path with four vertices, or a cycle with four vertices. A kite is the graph obtained from $K_4$ by deleting two adjacent edges, i.e., a triangle together with a pendant edge. The exact value of $f(H)$ when $H$ is the kite remains open. In this paper, we settle this problem by showing that every 7-connected graph is kite-linked.

Cognitive radio (CR) networks have an ample but dynamic amount of spectrum for communications. Communication rendezvous in CR networks is the process of establishing a control channel between radios before they can communicate. Designing a communication rendezvous protocol that can take advantage of all the available spectrum at the same time is of great importance, because it alleviates load on control channels, and thus further reduces probability of collisions. In this paper, we present ETCH, efficient channel-hopping-based MAC-layer protocols for communication rendezvous in CR networks. Compared to the existing solutions, ETCH fully exploits spectrum diversity in communication rendezvous by allowing all the rendezvous channels to be utilized at the same time. We propose two protocols, SYNC-ETCH, which is a synchronous protocol assuming CR nodes can synchronize their channel hopping processes, and ASYNC-ETCH, which is an asynchronous protocol not relying on global clock synchronization. Our theoretical analysis and ns-2-based evaluation show that ETCH achieves better performances of time-to-rendezvous and throughput than the existing work.

A graph is $(c_1, c_2, \ldots, c_k)$-colorable if the vertex set can be partitioned into $k$ sets $V_1,V_2, \ldots, V_k$, such that for every $i: 1\leq i\leq k$ the subgraph $G[V_i]$ has maximum degree at most $c_i$. We show that every planar graph without $4$- and $5$-cycles is $(1, 1, 0)$-colorable. This is a relaxation of the Steinberg conjecture that every planar graph without $4$- and $5$-cycles are properly $3$-colorable (i.e., $(0,0,0)$-colorable).

In a dynamic spectrum access (DSA) network, communication rendezvous is the first step for two secondary users to be able to communicate with each other. In this step, the pair of secondary users meet on the same channel, over which they negotiate on the communication parameters, to establish the communication link. This paper presents ETCH, Efficient Channel Hopping based MAC-layer protocols for communication rendezvous in DSA networks. We propose two protocols, SYNC-ETCH and ASYNC-ETCH. Both protocols achieve better time-to-rendezvous and throughput compared to previous work.

It was conjectured that a permutation matrix with bandwidth [Formula: see text] can be written as a product of no more than [Formula: see text] permutation matrices of bandwidth 1. In this note, two proofs are given to affirm the conjecture.

A proper vertex coloring of a graph G is equitable if the sizes of color classes differ by at most one. The equitable chromatic threshold $\chi_{eq}^*(G)$ of G is the smallest integer m such that G is equitably n-colorable for all $n\geq m$. We show that for planar graphs G with minimum degree at least two, $\chi_{eq}^*(G)\leq4$ if the girth of G is at least 10, and $\chi_{eq}^*(G)\leq3$ if the girth of G is at least 14.

A p-page embedding of a graph G is a vertex-ordering $\pi$ of $V(G)$ (along the “spine” of a book) and an assignment of edges to p half-planes (called “pages”) such that no page contains crossing edges (alternating endpoints) relative to $\pi$. The pagenumber of G is the least p such that G has a p-page embedding. We disprove a conjecture of Ganley and Heath by showing that when $k\geq3$, there are k-trees that do not embed in k pages. We also present an algorithm that produces k-page embeddings for k-trees in a special class.

The first-fit chromatic number of a graph is the number of colors needed in the worst case of a greedy coloring. It is also called the Grundy number, which is defined to be the maximum number of classes in an ordered partition of the vertex set of a graph G into independent sets $V_1, V_2, \dots, V_k$ so that for each $1\le i

Given a fixed multigraph H, possibly containing loops, with $V(H) = \{h_1,\ldots,h_m\}$, we say that a graph G is H‐linked if for every choice of m vertices $v_1,\ldots,v_m$ in G, there exists a subdivision of H in G such that $v_i$ is the branch vertex representing $h_i$ (for all i). This generalizes the concept of k‐linked graphs (as well as a number of other well‐known path or cycle properties). In this paper we determine a sharp lower bound on $\delta(G)$ (which depends upon H) such that each graph G on at least $10(|V(H)|+|E(H)|)$ vertices satisfying this bound is H‐linked.