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.     

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)=??.     

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.     

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).     

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.     

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.     

Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs

In this paper, we study the parameterized complexity of Dominating Set problem in chordal graphs and near chordal graphs. We show the problem is W[2]-hard and cannot be solved in time n ^o(k) in chordal and s-chordal (s>3) graphs unless W[1]=FPT. In addition, we obtain inapproximability results for computing a minimum dominating set in chordal and near chordal graphs. Our results prove that unless NP=P, the minimum dominating set in a chordal or s-chordal (s>3) graph cannot be approximated within a ratio of \fracc3lnn\frac{c}{3}\ln{n} in polynomial time, where n is the number of vertices in the graph and 0<c<1 is the constant from the inapproximability of the minimum dominating set in general graphs. In other words, our results suggest that restricting to chordal or s-chordal graphs can improve the approximation ratio by no more than a factor of 3. We then extend our techniques to find similar results for the Independent Dominating Set problem and the Connected Dominating Set problem in chordal or near chordal graphs.     

Does one hat fit all? The case of corporate leadership structure

Recent corporate scandals have led to renewed campaigns for governance reforms, including calls for the separation of CEO and chairman positions. This paper argues that this trend ignores the possibility that differences in firm characteristics determine the appropriateness of separating or combining the two positions. I propose and test hypotheses on the determinants of leadership structure using a sample of 1,883 firms. I find that organizational complexity, CEO reputation, and managerial ownership increase the probability of CEO duality. I also find that whether CEO duality benefits or hurts the firm is contingent on firm and CEO characteristics. These results suggest that firms do consider the costs and benefits of alternative leadership structures, and that requiring all firms to separate CEO and chairman duties may be counterproductive.

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.     

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).     

Do minimum wages increase job satisfaction? Micro‐data evidence from the new German minimum wage

On January 1, 2015, a new statutory minimum wage of € 8.50 per hour of work was introduced in Germany. Using a difference‐in‐differences approach, we estimate effects on worker‐level outcomes of continuing employees. The results reveal a meaningful absolute increase in the affected workers' pay satisfaction. The increase in job satisfaction is modest and predominantly driven by changes in pay satisfaction implying only a small effect on all other dimensions of job satisfaction. Moreover, effects from the minimum wage on work engagement and turnover intention are virtually zero.     

On certain geometric properties of the Yao–Yao graphs

We show that, for any constant $\rho > 1$ , there exists an integer constant $k$ such that the Yao–Yao graph with parameter $k$ defined on a civilized unit disk graph is a geometric spanner of stretch factor $\rho $ . This improves the results of Wang and Li in several aspects, as described in the paper. This partially answers an open problem posed by Demaine, Mitchell and O’Rourke about the spanner properties of Yao–Yao graphs. We also show that the Yao–Yao graph with parameter $k=4$ defined on the complete Euclidean graph is not plane.     

Socioemotional wealth’s implications in the calculus of the minimum rate of return required by family businesses’ owners

This paper demonstrates that the minimum rate of return (k _e ) required by family business shareholders is inversely related to the emotional endowment presented in these firms. After reviewing the socioemotional wealth (SEW) literature, we find empirical support to justify that different SEW dimensions influence k _e . Findings from a population of 207 family firms show that the identification of family members with the firm and the renewal of family bonds with the firm through dynastic succession have consistently negative impacts on k _e , while family control and influence have significantly positive impacts on k _e .     

Is HRD in need of an ethics of care?

Human Resource Development (HRD) operates within competitive global environments and the changing expectations of societal moral values, which can be in conflict with organizational values, performance, and profit. These are underpinned by the unquestioning acceptance and ‘orthodoxy’ of free‐market economics, legalism, and codes of conduct that result in a lack of ethical analysis within HRD practice. In response to the forgoing, it will be argued that the ethics of care that espouses the values of human relationships, empathy, dignity, and respect is a legitimate approach to free-market lead ethical rule-based rationality that is often presented as the de facto position for HRD professional practice. It presents the ethical debates in which HRD operates within, before arguing for the ethics of care. Three case examples from practice are offered illustrating how HRD practice might respond through the lens of an ethics of care. Reflections and implications for HRD in the form of objections and responses are considered. It concludes that HRD professionals are faced with many difficulties when making decisions, and that the ethics of care offer is an alternative perspective for HRD practitioners.     

Hardness results and approximation algorithm for total liar’s domination in graphs

In this paper, we initiate the study of total liar’s domination of a graph. A subset L?V of a graph G=(V,E) is called a total liar’s dominating set of G if (i) for all v∈V, |N _G (v)∩L|≥2 and (ii) for every pair u,v∈V of distinct vertices, |(N _G (u)∪N _G (v))∩L|≥3. The total liar’s domination number of a graph G is the cardinality of a minimum total liar’s dominating set of G and is denoted by γ _TLR (G). The Minimum Total Liar’s Domination Problem is to find a total liar’s dominating set of minimum cardinality of the input graph G. Given a graph G and a positive integer k, the Total Liar’s Domination Decision Problem is to check whether G has a total liar’s dominating set of cardinality at most k. In this paper, we give a necessary and sufficient condition for the existence of a total liar’s dominating set in a graph. We show that the Total Liar’s Domination Decision Problem is NP-complete for general graphs and is NP-complete even for split graphs and hence for chordal graphs. We also propose a 2(lnΔ(G)+1)-approximation algorithm for the Minimum Total Liar’s Domination Problem, where Δ(G) is the maximum degree of the input graph G. We show that Minimum Total Liar’s Domination Problem cannot be approximated within a factor of $(\frac{1}{8}-\epsilon)\ln(|V|)$ for any ?>0, unless NP?DTIME(|V|^loglog|V|). Finally, we show that Minimum Total Liar’s Domination Problem is APX-complete for graphs with bounded degree 4.     

Career patterns of top managers in Europe: Signs of further globalisation?

Investigating career patterns of top managers has been a prominent topic in European Management Journal (EMJ) since the 1990s. Our article contributes to ongoing debates about national differences in top managers' career patterns between European countries. An open question is whether globalisation processes may have challenged the existence of specific career patterns and whether they may have transformed the profiles of business elites in Europe. Our article uses recent data from four European countries (France, Germany, Switzerland and the UK), collected in a way similar to an EMJ article published in 2013, with the objective to assess potential developments that have taken place over the last decade. Some of the major changes relate to the growing relevance of business school degrees or certificates (such as MBA degrees), a higher proportion of non-nationals and women on boards, more managers with international experience and an increasing number of top managers with a prior career with auditing or consulting firms. The article provides not only new empirical insights, but also a review of the key characteristics of top managers’ careers, some methodological reflections on cross-national comparison and new research avenues at the cross-roads of career literature and upper echelons literature. By shedding light on the career patterns of key decision-makers in large European firms, the article offers new insights for researchers, educators and managers alike.     

Functional leadership in interteam contexts: Understanding ‘what’ in the context of why? where? when? and who?

Research on team leadership has primarily focused on leadership processes targeted within teams, in support of team objectives. Yet, teams are open systems that interact with other teams to achieve proximal as well as distal goals. This review clarifies that defining ‘what’ constitutes functionally effective leadership in interteam contexts requires greater precision with regard to where (within teams, across teams) and why (team goals, system goals) leadership processes are enacted, as well as greater consideration of when and among whom leadership processes arise. We begin by synthesizing findings from empirical studies published over the past 30 years that shed light on questions of what, where, why, when, and who related to interteam leadership and end by providing three overarching recommendations for how research should proceed in order to provide a more comprehensive picture of leadership in interteam contexts.     

Policy Theories in Hard Times? Assessing the Explanatory Power of Policy Theories in the Context of Crisis

Can the behavior of political actors in business-as-usual conditions be analyzed with the same theoretical framework as decision-making in situations characterized by uncertainty, ambiguity, complexity and urgency? After comparing major existing approaches and evaluating their explanatory logic under crisis circumstances, the present article develops a theoretical framework which explicitly accounts for the crisis characteristics at two stages of the policy making process, agenda-setting and decision-making. The bearing of policy-entrepreneurs, international networks, institutions and partisanship on policy outcomes critically depends on the specific workings on these levels in crisis-mode. These expectations are probed in an empirical re-evaluation of the 2011 Spanish pension reform.