Shifting strategy for geometric graphs without?geometry

We give a simple framework which is an alternative to the celebrated and widely used shifting strategy of Hochbaum and Maass (J. ACM 32(1):103?C136, 1985) which has yielded efficient algorithms with good approximation bounds for numerous optimization problems in low-dimensional Euclidean space. Our framework does not require the input graph/metric to have a geometric realization??it only requires that the input graph satisfy some weak property referred to as growth boundedness. Growth bounded graphs form an important graph class that has been used to model wireless networks. We show how to apply the framework to obtain a polynomial time approximation scheme (PTAS) for the maximum (weighted) independent set problem on this important graph class; the problem is W[1]-complete. Via a more sophisticated application of our framework, we show how to obtain a PTAS for the maximum (weighted) independent set for intersection graphs of (low-dimensional) fat objects that are expressed without geometry. Erlebach et al. (SIAM J. Comput. 34(6):1302?C1323, 2005) and Chan (J. Algorithms 46(2):178?C189, 2003) independently gave a PTAS for maximum weighted independent set problem for intersection graphs of fat geometric objects, say ball graphs, which required a geometric representation of the input. Our result gives a positive answer to a question of Erlebach et al. (SIAM J. Comput. 34(6):1302?C1323, 2005) who asked if a PTAS for this problem can be obtained without access to a geometric representation.     

On the adjacent vertex-distinguishing total chromatic numbers of the graphs with Δ (G) = 3

Let be a simple graph and T(G) be the set of vertices and edges of G. Let C be a k-color set. A (proper) total k-coloring f of G is a function such that no adjacent or incident elements of T(G) receive the same color. For any , denote . The total k-coloring f of G is called the adjacent vertex-distinguishing if for any edge . And the smallest number of colors is called the adjacent vertex-distinguishing total chromatic number of G. In this paper, we prove that for all connected graphs with maximum degree three. This is a step towards a conjecture on the adjacent vertex-distinguishing total coloring. MSC: 05C15     

Some results on the injective chromatic number of?graphs

A k-coloring of a graph G=(V,E) is a mapping c:V??{1,2,??,k}. The coloring c is injective if, for every vertex v??V, all the neighbors of v are assigned with distinct colors. The injective chromatic number ?? _i (G) of G is the smallest k such that G has an injective k-coloring. In this paper, we prove that every K ₄-minor free graph G with maximum degree ????1 has $\chi_{i}(G)\le \lceil \frac{3}{2}\Delta\rceil$ . Moreover, some related results and open problems are given.     

Is there any polynomial upper bound for the universal labeling of graphs?

A universal labeling of a graph G is a labeling of the edge set in G such that in every orientation \(\ell \) of G for every two adjacent vertices v and u, the sum of incoming edges of v and u in the oriented graph are different from each other. The universal labeling number of a graph G is the minimum number k such that G has universal labeling from \(\{1,2,\ldots , k\}\) denoted it by \(\overrightarrow{\chi _{u}}(G) \). We have \(2\Delta (G)-2 \le \overrightarrow{\chi _{u}} (G)\le 2^{\Delta (G)}\), where \(\Delta (G)\) denotes the maximum degree of G. In this work, we offer a provocative question that is: “Is there any polynomial function f such that for every graph G, \(\overrightarrow{\chi _{u}} (G)\le f(\Delta (G))\)?”. Towards this question, we introduce some lower and upper bounds on their parameter of interest. Also, we prove that for every tree T, \(\overrightarrow{\chi _{u}}(T)={\mathcal {O}}(\Delta ^3) \). Next, we show that for a given 3-regular graph G, the universal labeling number of G is 4 if and only if G belongs to Class 1. Therefore, for a given 3-regular graph G, it is an \( {{\mathbf {N}}}{{\mathbf {P}}} \)-complete to determine whether the universal labeling number of G is 4. Finally, using probabilistic methods, we almost confirm a weaker version of the problem.     

On the Langberg–Médard multiple unicast conjecture

A version of the multiple unicast conjecture, proposed by Langberg and Médard (in: Proceedings of 47th annual Allerton, 2009), says that, there exists an undirected fractional multi-commodity flow, or simply, multi-flow, with rate \((1,1,\ldots ,1)\) for strongly reachable networks. In this paper, we propose a nonsmooth matrix optimization problem to attack this conjecture: By giving upper and lower bounds on the objective value, we prove that there exists a multi-flow with rate at least \((\frac{8}{9}, \frac{8}{9}, \ldots , \frac{8}{9})\) for such networks; on the other hand though, we show that the rate of any multi-flow constructed using this framework cannot exceed \((1,1,\ldots ,1)\).     

Improved floor-planning of graphs via adjacency-preserving transformations

Let G=(V,E) and G′=(V′,E′) be two graphs, an adjacency-preserving transformation from G to G′ is a one-to-many and onto mapping from V to V′ satisfying the following: (1) Each vertex v∈V in G is mapped to a non-empty subset \(\mathcal{A}(v)\subset V'\) in G′. The subgraph induced by \(\mathcal{A}(v)\) is a connected subgraph of G′; (2) if u≠v∈V, then \(\mathcal{A}(u)\cap\mathcal{A}(v)=\emptyset\); and (3) two vertices u and v are adjacent to each other in G if and only if subgraphs induced by \(\mathcal{A}(u)\) and \(\mathcal{A}(v)\) are connected in G′.In this paper, we study adjacency-preserving transformations from plane triangulations to irreducible triangulations (which are internally triangulated, with four exterior vertices and no separating triangles). As one shall see, our transformations not only preserve adjacency well, but also preserve the endowed realizers of plane triangulations well in the endowed transversal structures of the image irreducible triangulations, which may be desirable in some applications.We then present such an application in floor-planning of plane graphs. The expected grid size of the floor-plan of our linear time algorithm is improved to \((\frac{5n}{8}+O(1))\times (\frac{23n}{24}+O(1))\), though the worst case grid size bound of the algorithm remains \(\lfloor\frac{2n+1}{3}\rfloor\times(n-1)\), which is the same as the algorithm presented in Liao et al. (J. Algorithms 48:441–451, 2003).     

The Wiener index of Sierpiński-like graphs

Sierpiński-like graphs constitute an extensively studied family of graphs of fractal nature applicable in topology, mathematics of the Tower of Hanoi, computer science, and elsewhere. In this paper, we focus on the Wiener polarity index, Wiener index and Harary index of Sierpiński-like graphs. By Sierpiński-like graphs’ special structure and correlation, their Wiener polarity index and some Sierpiński-like graph’s Wiener index and Harary index are obtained.     

Theories of the Firm–Market Boundary

A central role of the entrepreneur-manager is assembling a strategic bundle of complementary assets and activities, either existing or foreseen, which when combined create value for the firm. This process of creating value, however, requires managers to assess which activities should be handled by the market and which should be handled within hierarchy. Indeed, for more than 40 years, economists, sociologists and organizational scholars have extensively examined the theory of the firm's central question: what determines the boundaries of the firm? Many alternative theories have emerged and are frequently positioned as competing explanations, often with no shortage of critique for one another. In this paper, we review these theories and suggest that the core theories that have emerged to explain the boundary of the firm commonly address distinctly different directional forces on the firm boundary—forces that are tightly interrelated. We specifically address these divergent, directional forces—as they relate to organizational boundaries—by focusing on four central questions. First, what are the virtues of markets in organizing assets and activities? Second, what factors drive markets to fail? Third, what are the virtues of integration in organizing assets and activities? Fourth, what factors drive organizations to fail? We argue that a complete theory of the firm must address these four questions and we review the relevant literature regarding each of these questions and discuss extant debates and the associated implications for future research.     

Computing unique maximum matchings in $$$$ time for König–Egerváry graphs and unicyclic graphs

Let \(\alpha \left( G\right) \) denote the maximum size of an independent set of vertices and \(\mu \left( G\right) \) be the cardinality of a maximum matching in a graph \(G\). A matching saturating all the vertices is a perfect matching. If \(\alpha \left( G\right) +\mu \left( G\right) =\left| V(G)\right| \), then \(G\) is called a König–Egerváry graph. A graph is unicyclic if it is connected and has a unique cycle. It is known that a maximum matching can be found in \(O(m\cdot \sqrt{n})\) time for a graph with \(n\) vertices and \(m\) edges. Bartha (Proceedings of the 8th joint conference on mathematics and computer science, Komárno, Slovakia, 2010) conjectured that a unique perfect matching, if it exists, can be found in \(O(m)\) time. In this paper we validate this conjecture for König–Egerváry graphs and unicylic graphs. We propose a variation of Karp–Sipser leaf-removal algorithm (Karp and Sipser in Proceedings of the 22nd annual IEEE symposium on foundations of computer science, 364–375, 1981) , which ends with an empty graph if and only if the original graph is a König–Egerváry graph with a unique perfect matching (obtained as an output as well). We also show that a unicyclic non-bipartite graph \(G\) may have at most one perfect matching, and this is the case where \(G\) is a König–Egerváry graph.     

On the meaning of ‘Waste’: review and definition

Waste reduction is one of the main principles of lean, but it has been taken for granted that we have a common understanding of what waste means. We first present a critical, qualitative discussion that identifies four distinct waste concepts. We then conduct a systematic review of the literature that examines the different uses of these concepts. We find that only the classic concept of the seven wastes and the concept of waste as non-value-adding activity are widely applied. However, both concepts are, at times, not only incompatible but used in a way that leads to open contradiction. A new definition, centred on an efficient, timely transformation process seeks to consolidate the literature. We outline two distinct waste types: (i) obvious waste, to refer to any waste that can be reduced without creating another form of waste; and, (ii) buffer waste, to refer to any waste that cannot be reduced without creating another waste. The paper has important implications for practice. To reduce waste, managers must undertake three interlinked tasks: the elimination of obvious waste; the reduction of variability to transform buffers into obvious waste; and, the balancing of remaining buffers to best achieve performance targets. The paper supports managers in their endeavours to identify waste, which is an important precursor to waste reduction/elimination.     

Adjacent vertex-distinguishing edge coloring of graphs with maximum degree Δ

An adjacent vertex-distinguishing edge coloring, or avd-coloring, of a graph G is a proper edge coloring of G such that no pair of adjacent vertices meets the same set of colors. Let $\operatorname {mad}(G)$ and Δ(G) denote the maximum average degree and the maximum degree of a graph G, respectively. In this paper, we prove that every graph G with Δ(G)≥5 and $\operatorname{mad}(G) < 3-\frac {2}{\Delta}$ can be avd-colored with Δ(G)+1 colors. This completes a result of Wang and Wang (J. Comb. Optim. 19:471–485, 2010).     

Vertices in all minimum paired-dominating sets of?block graphs

Let G=(V,E) be a simple graph without isolated vertices. A set S?V is a paired-dominating set if every vertex in V?S has at least one neighbor in S and the subgraph induced by S contains a perfect matching. In this paper, we present a linear-time algorithm to determine whether a given vertex in a block graph is contained in all its minimum paired-dominating sets.     

On irreducible no-hole <Emphasis Type="Italic">L</Emphasis>(2, 1)-coloring of subdivision of graphs

An L(2, 1)-coloring (or labeling) of a graph G is a mapping \(f:V(G) \rightarrow \mathbb {Z}^{+}\bigcup \{0\}\) such that \(|f(u)-f(v)|\ge 2\) for all edges uv of G, and \(|f(u)-f(v)|\ge 1\) if u and v are at distance two in G. The span of an L(2, 1)-coloring f, denoted by span f, is the largest integer assigned by f to some vertex of the graph. The span of a graph G, denoted by \(\lambda (G)\), is min {span \(f: f\text {is an }L(2,1)\text {-coloring of } G\}\). If f is an L(2, 1)-coloring of a graph G with span k then an integer l is a hole in f, if \(l\in (0,k)\) and there is no vertex v in G such that \(f(v)=l\). A no-hole coloring is defined to be an L(2, 1)-coloring with span k which uses all the colors from \(\{0,1,\ldots ,k\}\), for some integer k not necessarily the span of the graph. An L(2, 1)-coloring is said to be irreducible if colors of no vertices in the graph can be decreased and yield another L(2, 1)-coloring of the same graph. An irreducible no-hole coloring of a graph G, also called inh-coloring of G, is an L(2, 1)-coloring of G which is both irreducible and no-hole. The lower inh-span or simply inh-span of a graph G, denoted by \(\lambda _{inh}(G)\), is defined as \(\lambda _{inh}(G)=\min ~\{\)span f : f is an inh-coloring of G}. Given a graph G and a function h from E(G) to \(\mathbb {N}\), the h-subdivision of G, denoted by \(G_{(h)}\), is the graph obtained from G by replacing each edge uv in G with a path of length h(uv). In this paper we show that \(G_{(h)}\) is inh-colorable for \(h(e)\ge 2\), \(e\in E(G)\), except the case \(\Delta =3\) and \(h(e)=2\) for at least one edge but not for all. Moreover we find the exact value of \(\lambda _{inh}(G_{(h)})\) in several cases and give upper bounds of the same in the remaining.     

The changing role of the supervisory board chairman: the case of the Netherlands (1997–2007)

Over the last ten years, the corporate governance context in most Western countries has changed as a result of irregularities, increased regulation, heightened societal expectations and shareholder activism. This paper examines the impact of the changing context on the role of chairmen of supervisory boards in the Netherlands. Based on a combination of thirty semi-structured interviews with board members of leading Dutch corporations and secondary data on the position of supervisory board chairmen at the top-100 listed firms in the Netherlands, the study reveals that board chairmen have become increasingly involved in both their control and service roles. While the demographics (i.e., age, tenure, gender and nationality) of chairmen have hardly changed over the last decade, chairmen are spending considerably more time on boards and committees, have reduced the number of board interlocks and have become more active on the forefront of the corporate governance discussion. The paper highlights several implications for scholars and practitioners.     

An empirical examination of the science–technology relationship in the biotechnology industry

Understanding how a firm's scientific capability influences its technology development has important implications on the firm's research and development (R&D) strategies. However, the current literature reveals a puzzling outcome in its empirical investigations on the science–technology relationship. While many studies show the positive influence of a firm's scientific capability on its technological performance, a few others indicate that if a firm focuses its attention more on cutting edge science, its overall technological performance will suffer. We suggest that these findings can be reconciled by conceptualizing and measuring the scientific capability of the firm differently. This paper attempts to demonstrate how different notions of scientific capability are associated with different performance outcomes. Furthermore, a firm's scientific capability facilitates the integration of new knowledge to produce valuable technologies when a firm broadens its search for new knowledge. The paper highlights the nuances of conceptualizing and measuring the firm's scientific capability in two different ways: number of scientific publications and non-patent references. The findings also shed light on the mechanism through which science accelerates technological progress inside a firm.     

Detrimental Effects of Performance-Related Pay in the Public Sector? On the Need for a Broader Theoretical Perspective

Performance-related pay has been a key ingredient in New Public Management reforms. Nevertheless, the research presented here indicates some adverse effects of such incentives. These incentives may impair an initial motivation to work and change the norms that guide behavior. An issue which in particular has been given insufficient attention is fairness. Findings drawn from experimental economics supported by field studies demonstrate that perceived unfairness may have important negative effects on performance. The implication of a broader perspective in the analysis of performance-related pay in the public sector is that such a pay system, contrary to its aim, may have detrimental effects on performance.     

Fibonacci index and stability number of graphs: a polyhedral study

The Fibonacci index of a graph is the number of its stable sets. This parameter is widely studied and has applications in chemical graph theory. In this paper, we establish tight upper bounds for the Fibonacci index in terms of the stability number and the order of general graphs and connected graphs. Turán graphs frequently appear in extremal graph theory. We show that Turán graphs and a connected variant of them are also extremal for these particular problems. We also make a polyhedral study by establishing all the optimal linear inequalities for the stability number and the Fibonacci index, inside the classes of general and connected graphs of order n.     

On the <Emphasis Type="Italic">L</Emphasis>(2, 1)-labeling conjecture for brick product graphs

Let \(G=(V, E)\) be a graph. Denote \(d_G(u, v)\) the distance between two vertices u and v in G. An L(2, 1)-labeling of G is a function \(f: V \rightarrow \{0,1,\ldots \}\) such that for any two vertices u and v, \(|f(u)-f(v)| \ge 2\) if \(d_G(u, v) = 1\) and \(|f(u)-f(v)| \ge 1\) if \(d_G(u, v) = 2\). The span of f is the difference between the largest and the smallest number in f(V). The \(\lambda \)-number \(\lambda (G)\) of G is the minimum span over all L(2, 1)-labelings of G. In this paper, we conclude that the \(\lambda \)-number of each brick product graph is 5 or 6, which confirms Conjecture 6.1 stated in Li et al. (J Comb Optim 25:716–736, 2013).     

Acyclic chromatic indices of planar graphs with girth at?least five

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a??(G) of G is the smallest integer k such that G has an acyclic edge coloring using k colors. In this paper, we prove that every planar graph G with girth g(G)??5 and maximum degree ????12 has a??(G)=??.