Art galleries with guards of uniform range of vision

We are given an art gallery represented by a simple polygon with n sides and an angle (0°,360°]. How many guards of range of vision are required to monitor every point of the polygon in the worst case? After recent results on upper bounds of this problem, we prove new lower bounds for all 0°<<180°. Several lower bounds meet the best known upper bounds, and we expect our lower bounds to be best possible.

Surprisingly, it turns out that n/3 180°-guards are always enough to monitor a polygon of n sides, but if we wish to use (180−)°-guards for any >0, then possibly 2n/3−1 guards are necessary.     

Art gallery problem with guards whose range of vision is 180

It is shown that in any polygonal art gallery of n sides it is possible to place n/3 point guards whose range of vision is 180° so that every interior point of the gallery can be seen by at least one of them. The guards can be stationed at any point of the art gallery. This settles an open problem posed by J. Urrutia.     

Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight

A graph H is defined to be light in a family H of graphs if there exists a finite number φ(H,H) such that each G∈H which contains H as a subgraph, contains also a subgraph K≅H such that the Δ_G(K)≤φ(H,H). We study light graphs in families of polyhedral graphs with prescribed minimum vertex degree δ, minimum face degree ρ, minimum edge weight w and dual edge weight w^∗. For those families, we show that there exists a variety of small light cycles; on the other hand, we also present particular constructions showing that, for certain families, the spectrum of short cycles contains irregularly scattered cycles that are not light.     

Edge agreement of second-order multi-agent system with dynamic quantization via the directed edge Laplacian

This work explores the edge agreement problem of second-order multi-agent systems with dynamic quantization under directed communication. To begin with, by virtue of the directed edge Laplacian, we propose a model reduction representation of the closed-loop multi-agent system depending on the spanning tree subgraph. Considering the limitations of the finite bandwidth channels, the quantization effects of second-order multi-agent systems under directed graph are considered. The static quantizers generally contain a fixed quantization interval and infinite quantization level, which are, to some extent, inefficient and impractical. To further reduce the bit depth (number of bits available) and to obtain better precision, the dynamic quantized communication strategy referring to zooming in-zooming out scheme is required. Based on the reduced model associated with the essential edge Laplacian, the asymptotic stability of second-order multi-agent systems under dynamic quantized effects with only finite quantization level can be guaranteed. Finally, the simulation of altitude alignment of micro air vehicles is provided to verify the theoretical results.     

On minimally 2-(edge)-connected graphs with extremal spectral radius

A graph is minimally 2-(edge)-connected if it is 2-(edge)-connected and deleting any arbitrary chosen edge always leaves a graph which is not 2-(edge)-connected. In this paper, we completely characterize the minimally 2-(edge)-connected graphs having the largest and the smallest spectral radius, respectively.     

Edge partitions of optimal 2-plane and 3-plane graphs

A topological graph is a graph drawn in the plane. A topological graph is $k$-plane, $k>0$, if each edge is crossed at most $k$ times. We study the problem of partitioning the edges of a $k$-plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for $k=1$, we focus on optimal 2-plane and on optimal 3-plane graphs, which are 2-plane and 3-plane graphs with maximum density. We prove the following results. (i) It is not possible to partition the edges of a simple (i.e., with neither self-loops nor parallel edges) optimal 2-plane graph into a 1-plane graph and a forest, while (ii) an edge partition formed by a 1-plane graph and two plane forests always exists and can be computed in linear time. (iii) There exist efficient algorithms to partition the edges of a simple optimal 2-plane graph into a 1-plane graph and a plane graph with maximum vertex degree at most 12, or with maximum vertex degree at most 8 if the optimal2-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) There exists an infinite family of simple optimal 2-plane graphs such that in any edge partition composed of a 1-plane graph and a plane graph, the plane graph has maximum vertex degree at least 6 and the 1-plane graph has maximum vertex degree at least 12. (v) Every optimal 3-plane graph whose crossing-free edges form a biconnected graph can be decomposed, in linear time, into a 2-plane graph and two plane forests.     

Acyclic edge coloring of 2‐degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). A graph is called 2‐degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphs properly contains series–parallel graphs, outerplanar graphs, non ? regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G)?Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. We prove the conjecture for 2‐degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2‐degenerate graph with maximum degree Δ, then a′(G)?Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012     

Control of multi-node mobile communications networks with time-varying channels via stability methods

Consider a communications network consisting of mobiles and random external data processes, each destined to a particular destination. Each mobile can serve as a node in the multi-hop path from source to destination. At each mobile the data is queued according to the source destination pair. The quality of the connecting channels are randomly varying. Time is divided into small scheduling intervals. At the beginning of each interval, the channels are estimated and this information is used for the decisions concerning allocation of transmission power and/or time, bandwidth, and perhaps antennas, in a queue and channel-state dependent way. Under a natural (and “almost” necessary) “average flow” condition, stochastic stability methods are used to develop scheduling policies that assure stability. The policies are readily implementable and allow a range of tradeoffs between current rates and queue lengths, under very weak conditions. Because of the non-Markovian nature of the problem, we use the perturbed Stochastic Liapunov function method. The choice of Liapunov function allows a choice of the effective performance criteria. All essential factors are incorporated into a “mean rate” function, so that the results cover many different systems. Extensions concerning acknowledgments, multicasting, non-unique routes, and others are given to illustrate the versatility of the method, and a useful method for getting the a priori routes is discussed.     

Decomposition of cubic graphs with a 2-factor consisting of three cycles

The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular subgraph and a matching. We prove that this conjecture is true for connected cubic graphs with a 2-factor consisting of three cycles.     

Note on 2-edge-colorings of complete graphs with small monochromatic k-connected subgraphs

Bollob′as and Gy′arf′as conjectured that for n4(k-1) every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n-2k+2 verticesLiu, et alproved that the conjecture holds when n≥13k-15In this note, we characterize all the2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n-2k+2 vertices for n≥13k-15.     

Classification of a family of symmetric graphs with complete 2-arc-transitive quotients

In this paper we give a classification of a family of symmetric graphs with complete 2-arc-transitive quotients. Of particular interest are two subfamilies of graphs which admit an arc-transitive action of a projective linear group. The graphs in these subfamilies can be defined in terms of the cross ratio of certain 4-tuples of elements of a finite projective line, and thus may be called the second type ‘cross ratio graphs’, which are different from the ‘cross ratio graphs’ studied in [A. Gardiner, C. E. Praeger, S. Zhou, Cross-ratio graphs, J. London Math. Soc. (2) 64 (2001), 257–272]. We also give a combinatorial characterisation of such second type cross ratio graphs.     

On the characterization of trees with signed edge domination numbers 1, 2, 3, or 4

Let G=(V,E) be a simple graph. For an edge e of G, the closed edge-neighbourhood of e is the set N[e]={e^′∈E|e^′ is adjacent to e}∪{e}. A function f:E→{1,−1} is called a signed edge domination function (SEDF) of G if ∑_e^′∈N[e]f(e^′)≥1 for every edge e of G. The signed edge domination number of G is defined as . In this paper, we characterize all trees T with signed edge domination numbers 1, 2, 3, or 4.     

Closed 2-cell embeddings of graphs with no V8-minors

A closed 2-cell embedding of a graph embedded in some surface is an embedding such that each face is bounded by a cycle in the graph. The strong embedding conjecture says that every 2-connected graph has a closed 2-cell embedding in some surface. In this paper, we prove that any 2-connected graph without V₈ (the Möbius 4-ladder) as a minor has a closed 2-cell embedding in some surface. As a corollary, such a graph has a cycle double cover. The proof uses a classification of internally-4-connected graphs with no V₈-minor (due to Kelmans and independently Robertson), and the proof depends heavily on such a characterization.     

不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界

图G的一个边分解是指将G分解成子图G_1,G_2,…,G_m使得E(G)=E(G_1)=∪E(G_2)∪…∪E(G_m),且对于i≠j,E(G_i)∩E(G_j)=?.一个线性k-森林是指每个分支都是长度最多为k的路的图.图G的线性k-荫度la_k(G)是使得G可以边分解为m个线性k-森林的最小整数m.显然,la_1(G)是G的边色数χ'(G); la_∞(G)表示每条分支路是无限长度时的情况,即通常所说的G的线性荫度la(G).利用权转移的方法研究平面图的线性2-荫度la_2(G).设G是不含有5-圈和相邻4-圈的平面图,证明了若G连通且δ(G)≥2,则G包含一条边xy使得d(x)+d(y)≤8或包含一个2-交错圈.根据这一结果得到其线性2-荫度的上界为[△/2]+4.