Convex partitions with 2-edge connected dual graphs

It is shown that for every finite set of disjoint convex polygonal obstacles in the plane, with a total of n vertices, the free space around the obstacles can be partitioned into open convex cells whose dual graph (defined below) is 2-edge connected. Intuitively, every edge of the dual graph corresponds to a pair of adjacent cells that are both incident to the same vertex.     

On the number of separable partitions

Consider partitions of a given set A of n distinct points in general position in ℝ ^d into parts where each pair of parts can be separated by a hyperplane that contains a given set of points E. We consider the problem of counting and generating all such partitions (correcting a classic 1967 result of Harding about the number of such partitions into two parts). Applications of the result to partition problems are presented.     

On backbone coloring of graphs

Let G be a graph and H a subgraph of G. A backbone-k-coloring of (G,H) is a mapping f: V(G)→{1,2,…,k} such that |f(u)−f(v)|≥2 if uv∈E(H) and |f(u)−f(v)|≥1 if uv∈E(G)\E(H). The backbone chromatic number of (G,H) is the smallest integer k such that (G,H) has a backbone-k-coloring. In this paper, we characterize the backbone chromatic number of Halin graphs G=T∪C with respect to given spanning trees T. Also we study the backbone coloring for other special graphs such as complete graphs, wheels, graphs with small maximum average degree, graphs with maximum degree 3, etc.     

On broadcasting in unicyclic graphs

Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Finding the broadcast time of a vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for trees. In this paper we present a linear algorithm that determines the broadcast time of any originator in an arbitrary unicyclic graph. As a byproduct, we find a broadcast center of the unicyclic graph. We also present an O(|V|+k ²) algorithm to find the broadcast time of an arbitrary unicyclic graph, where k is the length of the cycle. In the last section we give tight lower and upper bounds on broadcast time of a spanning tree based on the broadcast time of the unicyclic graph. The results of Sects. 2, 3 and most of the proofs in Sects. 2, 3 of this paper are presented by Harutyunyan and Maraachlian (Proceedings of 13th annual COCOON, pp. 372–383, 2007). All results in Sects. 4, 5 and the complete proof of Theorem 3 are new results.     

On total weight choosability of graphs

For a graph G with vertex set V and edge set E, a (k,k′)-total list assignment L of G assigns to each vertex v a set L(v) of k real numbers as permissible weights, and assigns to each edge e a set L(e) of k′ real numbers as permissible weights. If for any (k,k′)-total list assignment L of G, there exists a mapping f:V∪E→? such that f(y)∈L(y) for each y∈V∪E, and for any two adjacent vertices u and v, ∑ _y∈N(u) f(uy)+f(u)≠∑ _x∈N(v) f(vx)+f(v), then G is (k,k′)-total weight choosable. It is conjectured by Wong and Zhu that every graph is (2,2)-total weight choosable, and every graph with no isolated edges is (1,3)-total weight choosable. In this paper, it is proven that a graph G obtained from any loopless graph H by subdividing each edge with at least one vertex is (1,3)-total weight choosable and (2,2)-total weight choosable. It is shown that s-degenerate graphs (with s≥2) are (1,2s)-total weight choosable. Hence planar graphs are (1,10)-total weight choosable, and outerplanar graphs are (1,4)-total weight choosable. We also give a combinatorial proof that wheels are (2,2)-total weight choosable, as well as (1,3)-total weight choosable.     

On metric dimension of permutation graphs

The metric dimension \(\dim (G)\) of a graph \(G\) is the minimum number of vertices such that every vertex of \(G\) is uniquely determined by its vector of distances to the set of chosen vertices. Let \(G_1\) and \(G_2\) be disjoint copies of a graph \(G\) , and let \(\sigma : V(G_1) \rightarrow V(G_2)\) be a permutation. Then, a permutation graph \(G_{\sigma }=(V, E)\) has the vertex set \(V=V(G_1) \cup V(G_2)\) and the edge set \(E=E(G_1) \cup E(G_2) \cup \{uv \mid v=\sigma (u)\}\) . We show that \(2 \le \dim (G_{\sigma }) \le n-1\) for any connected graph \(G\) of order \(n\) at least \(3\) . We give examples showing that neither is there a function \(f\) such that \(\dim (G) for all pairs \((G,\sigma )\) , nor is there a function \(g\) such that \(g(\dim (G))>\dim (G_{\sigma })\) for all pairs \((G, \sigma )\) . Further, we characterize permutation graphs \(G_{\sigma }\) satisfying \(\dim (G_{\sigma })=n-1\) when \(G\) is a complete \(k\) -partite graph, a cycle, or a path on \(n\) vertices.     

On the b-coloring of tight graphs

A coloring c of a graph \(G=(V,E)\) is a b -coloring if for every color i there is a vertex, say w(i), of color i whose neighborhood intersects every other color class. The vertex w(i) is called a b-dominating vertex of color i. The b -chromatic number of a graph G, denoted by b(G), is the largest integer k such that G admits a b-coloring with k colors. Let m(G) be the largest integer m such that G has at least m vertices of degree at least \(m-1\). A graph G is tight if it has exactly m(G) vertices of degree \(m(G)-1\), and any other vertex has degree at most \(m(G)-2\). In this paper, we show that the b-chromatic number of tight graphs with girth at least 8 is at least \(m(G)-1\) and characterize the graphs G such that \(b(G)=m(G)\). Lin and Chang (2013) conjectured that the b-chromatic number of any graph in \(\mathcal {B}_{m}\) is m or \(m-1\) where \(\mathcal {B}_{m}\) is the class of tight bipartite graphs \((D,D{^\prime })\) of girth 6 such that D is the set of vertices of degree \(m-1\). We verify the conjecture of Lin and Chang for some subclass of \(\mathcal {B}_{m}\), and we give a lower bound for any graph in \(\mathcal {B}_{m}\).     

On minimum balanced bipartitions of triangle-free graphs

A balanced bipartition of a graph G is a partition of V(G) into two subsets V ₁ and V ₂ that differ in cardinality by at most 1. A minimum balanced bipartition of G is a balanced bipartition V ₁, V ₂ of G minimizing e(V ₁,V ₂), where e(V ₁,V ₂) is the number of edges joining V ₁ and V ₂ and is usually referred to as the size of the bipartition. In this paper, we show that every 2-connected graph G admits a balanced bipartition V ₁,V ₂ such that the subgraphs of G induced by V ₁ and by V ₂ are both connected. This yields a good upper bound to the size of minimum balanced bipartition of sparse graphs. We also present two upper bounds to the size of minimum balanced bipartitions of triangle-free graphs which sharpen the corresponding bounds of Fan et al. (Discrete Math. 312:1077–1083, 2012).     

On the outer-connected domination in graphs

A set S of vertices of a graph G is an outer-connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by V?S is connected. The outer-connected domination number $\widetilde{\gamma}_{c}(G)$ is the minimum size of such a set. We prove that if δ(G)≥2 and diam?(G)≤2, then $\widetilde{\gamma}_{c}(G)\le (n+1)/2$ , and we study the behavior of $\widetilde{\gamma}_{c}(G)$ under an edge addition.     

On cubic 2-independent Hamiltonian connected graphs

A graph G=(V,E) is Hamiltonian connected if there exists a Hamiltonian path between any two vertices in G. Let P ₁=(u ₁,u ₂,…,u _|V|) and P ₂=(v ₁,v ₂,…,v _|V|) be any two Hamiltonian paths of G. We say that P ₁ and P ₂ are independent if u ₁=v ₁,u _|V|=v _|V|, and u _i ≠v _i for 1<i<|V|. A cubic graph G is 2-independent Hamiltonian connected if there are two independent Hamiltonian paths between any two different vertices of G. A graph G is 1-Hamiltonian if G−F is Hamiltonian for any F⊆V∪E with |F|=1. A graph G is super 3^*-connected if there exist i internal disjoint paths spanning G for i=1,2,3. It is proved that every super 3^*-connected graph is 1-Hamiltonian. In this paper, we prove that every cubic 2-independent Hamiltonian connected graph is also 1-Hamiltonian. We present some cubic 2-independent Hamiltonian connected graphs that are super 3^*-connected, some cubic 2-independent Hamiltonian connected graphs that are not super 3^*-connected, some super 3^*-connected graphs that are not 2-independent Hamiltonian connected, and some cubic 1-Hamiltonian graphs that are Hamiltonian connected but neither 2-independent Hamiltonian connected nor super 3^*-connected. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work was supported in part by the National Science Council of the Republic of China under Contract NSC 94-2213-E-233-011.     

On the total outer-connected domination in graphs

A set S of vertices of a graph G is a total outer-connected dominating set if every vertex in V(G) is adjacent to some vertex in S and the subgraph induced by V?S is connected. The total outer-connected domination number γ _toc (G) is the minimum size of such a set. We give some properties and bounds for γ _toc in general graphs and in trees. For graphs of order n, diameter 2 and minimum degree at least 3, we show that $\gamma_{toc}(G)\le \frac{2n-2}{3}$ and we determine the extremal graphs.     

On the coefficients of the independence polynomial of graphs

An independent set of a graph G is a set of pairwise non-adjacent vertices. Let \(i_k = i_k(G)\) be the number of independent sets of cardinality k of G. The independence polynomial \(I(G, x)=\sum _{k\geqslant 0}i_k(G)x^k\) defined first by Gutman and Harary has been the focus of considerable research recently, whereas \(i(G)=I(G, 1)\) is called the Merrifield–Simmons index of G. In this paper, we first proved that among all trees of order n,  the kth coefficient \(i_k\) is smallest when the tree is a path, and is largest for star. Moreover, the graph among all trees of order n with diameter at least d whose all coefficients of I(G, x) are largest is identified. Then we identify the graphs among the n-vertex unicyclic graphs (resp. n-vertex connected graphs with clique number \(\omega \)) which simultaneously minimize all coefficients of I(G, x), whereas the opposite problems of simultaneously maximizing all coefficients of I(G, x) among these two classes of graphs are also solved respectively. At last we characterize the graph among all the n-vertex connected graph with chromatic number \(\chi \) (resp. vertex connectivity \(\kappa \)) which simultaneously minimize all coefficients of I(G, x). Our results may deduce some known results on Merrifield–Simmons index of graphs.     

On total and edge coloring some Kneser graphs

Journal of Combinatorial Optimization - In this work, we investigate the total and edge colorings of the Kneser graphs K(n,&nbsp;s). We prove that the sparse case of Kneser graphs, the odd...     

On colour-blind distinguishing colour pallets in regular graphs

Consider a graph \(G=(V,E)\) and a colouring of its edges with \(k\) colours. Then every vertex \(v\in V\) is associated with a ‘pallet’ of incident colours together with their frequencies, which sum up to the degree of \(v\) . We say that two vertices have distinct pallets if they differ in frequency of at least one colour. This is always the case if these vertices have distinct degrees. We consider an apparently the worse case, when \(G\) is regular. Suppose further that this coloured graph is being examined by a person who cannot name any given colour, but distinguishes one from another. Could we colour the edges of \(G\) so that a person suffering from such colour-blindness is certain that colour pallets of every two adjacent vertices are distinct? Using the Lopsided Lovász Local Lemma, we prove that it is possible using 15 colours for every \(d\) -regular graph with \(d\ge 960\) .     

Strongly 2-shape-sortability of vector partitions

Partitioning points optimally in ℝ¹ have been well studied. Hwang et al. (2003) first extended the optimal partitioning problems from ℝ¹ to ℝ^d. In particular, they studied the “sortability” of some partition properties. They also constructed examples to show that some partition properties, like Disjoint and Cone disjoint, are not sortable under some constraints 핊. In this note we construct a more concise example than theirs and also prove that another partition property, Nonpenetrating, is not sortable under 핊.     

On L(2,1)-labeling of generalized Petersen graphs

A variation of the classical channel assignment problem is to assign a radio channel which is a nonnegative integer to each radio transmitter so that ??close?? transmitters must receive different channels and ??very close?? transmitters must receive channels that are at least two channels apart. The goal is to minimize the span of a feasible assignment. This channel assignment problem can be modeled with distance-dependent graph labelings. A k-L(2,1)-labeling of a graph G is a mapping f from the vertex set of G to the set {0,1,2,??,k} such that |f(x)?f(y)|??2 if d(x,y)=1 and $f(x)\not =f(y)$ if d(x,y)=2, where d(x,y) is the distance between vertices x and y in G. The minimum k for which G admits an k-L(2,1)-labeling, denoted by ??(G), is called the ??-number of G. Very little is known about ??-numbers of 3-regular graphs. In this paper we focus on an important subclass of 3-regular graphs called generalized Petersen graphs. For an integer n??3, a graph G is called a generalized Petersen graph of order n if and only if G is a 3-regular graph consisting of two disjoint cycles (called inner and outer cycles) of length n, where each vertex of the outer (resp. inner) cycle is adjacent to exactly one vertex of the inner (resp. outer) cycle. In 2002, Georges and Mauro conjectured that ??(G)??7 for all generalized Petersen graphs G of order n??7. Later, Adams, Cass and Troxell proved that Georges and Mauro??s conjecture is true for orders 7 and 8. In this paper it is shown that Georges and Mauro??s conjecture is true for generalized Petersen graphs of orders 9, 10, 11 and 12.     

On consecutive edge magic total labelings of connected bipartite graphs

Since Sedlá\(\breve{\hbox {c}}\)ek introduced the notion of magic labeling of a graph in 1963, a variety of magic labelings of a graph have been defined and studied. In this paper, we study consecutive edge magic labelings of a connected bipartite graph. We make a useful observation that there are only four possible values of b for which a connected bipartite graph has a b-edge consecutive magic labeling. On the basis of this fundamental result, we deduce various interesting results on consecutive edge magic labelings of bipartite graphs. As a matter of fact, we do not focus just on specific classes of graphs, but also discuss the more general classes of non-bipartite and bipartite graphs.     

On the power domination number of the generalized Petersen graphs

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. Following a set of rules for power system monitoring, a set S of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S. The minimum cardinality of a power dominating set of G is the power domination number γ _p (G). In this paper, we investigate the power domination number for the generalized Petersen graphs, presenting both upper bounds for such graphs and exact results for a subfamily of generalized Petersen graphs.