Rainbow connection numbers of Cayley graphs

An edge colored graph is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number, rc-number for short, of a graph \({\varGamma }\), is the smallest number of colors that are needed in order to make \({\varGamma }\) rainbow connected. In this paper, we give a method to bound the rc-numbers of graphs with certain structural properties. Using this method, we investigate the rc-numbers of Cayley graphs, especially, those defined on abelian groups and on dihedral groups.     

Monotonicity of strong searching on digraphs

Given a digraph, suppose that some intruders hide on vertices or along edges of the digraph. We want to find the minimum number of searchers required to capture all the intruders hiding in the digraph. In this paper, we propose and study two digraph searching models: strong searching and mixed strong searching. In these two search models, searchers can move either from tail to head or from head to tail when they slide along edges, but intruders must follow the edge directions when they move along edges. We prove the monotonicity of each model respectively, and show that both searching problems are NP-complete. The research of B. Yang was supported in part by NSERC and MITACS.     

The hamiltonian numbers in digraphs

In the paper, we study the hamiltonian numbers in digraphs. A hamiltonian walk of a digraph D is a closed spanning directed walk with minimum length in D. The length of a hamiltonian walk of a digraph D is called the hamiltonian number of D, denoted h(D). We prove that if a digraph D of order n is strongly connected, then $n\leq h(D)\leq\lfloor\frac{(n+1)^{2}}{4} \rfloor$ , and hence characterize the strongly connected digraphs of order n with hamiltonian number $\lfloor\frac{(n+1)^{2}}{4} \rfloor$ . In addition, we show that for each k with $4\leq n\leq k\leq\lfloor \frac{(n+1)^{2}}{4} \rfloor$ , there exists a digraph with order n and hamiltonian number k. Furthermore, we also study the hamiltonian spectra of graphs.     

On cyclic vertex-connectivity of Cartesian product digraphs

For a strongly connected digraph D=(V(D),A(D)), a?vertex-cut S?V(D) is a cyclic vertex-cut of D if D?S has at least two strong components containing directed cycles. The cyclic vertex-connectivity ?? _c (D) is the minimum cardinality of all cyclic vertex-cuts of D. In this paper, we study ?? _c (D) for Cartesian product digraph D=D ₁×D ₂, where D ₁,D ₂ are two strongly connected digraphs. We give an upper bound and a lower bound for ?? _c (D). Furthermore, the exact value of $\kappa_{c}(C_{n_{1}}\times C_{n_{2}}\times\cdots\times C_{n_{k}})$ is determined, where $C_{n_{i}}$ is the directed cycle of length n _i for i=1,2,??,k.     

Maximum size of digraphs with some parameters

In this paper, we determine the maximum sizes of strong digraphs under the constraint that their some parameters are fixed, such as vertex connectivity, edge-connectivity, the number of cut vertices. The corresponding extremal digraphs are also characterized. In addition, we establish Nordhaus–Gaddum type theorem for the diameter when \(\overrightarrow{K_n}\) decomposing into many parts. We also pose a related conjecture for Wiener index of digraphs.     

Integral packing of branchings in capacitaded digraphs

We prove that an algorithm of Schrijver, that computes an integral packing of branchings in a capacitaded digraph, produces a packing with no more than \(m + r - 1\) different branchings, where \(m\) is the number of arcs, and \(r\) the number of root-sets of the digraph.     

Equitable vertex arboricity of 5-degenerate graphs

Wu et al. (Discret Math 313:2696–2701, 2013) conjectured that the vertex set of any simple graph G can be equitably partitioned into m subsets so that each subset induces a forest, where \(\Delta (G)\) is the maximum degree of G and m is an integer with \(m\ge \lceil \frac{\Delta (G)+1}{2}\rceil \). This conjecture is verified for 5-degenerate graphs in this paper.     

Sizes and transmissions of digraphs with a given clique number

We determine the maximum and minimum sizes of digraphs with a given clique numbers as well as the digraphs that attain these extremal sizes. The maximum and minimum transmissions of connected digraphs with given clique numbers are also determined.     

Adjacent vertex distinguishing total colorings of outerplanar graphs

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing total coloring of G is denoted by χ″ _a (G). In this paper, we characterize completely the adjacent vertex distinguishing total chromatic number of outerplanar graphs.     

Adjacent vertex distinguishing edge coloring of IC-planar graphs

Journal of Combinatorial Optimization - The adjacent vertex distinguishing edge coloring of a graph G is a proper edge coloring in which each pair of adjacent vertices is assigned different color...     

On the vertex characterization of single-shape partition polytopes

Given a partition of distinct d-dimensional vectors into p parts, the partition sum of the partition is the sum of vectors in each part. The shape of the partition is a p-tuple of the size of each part. A single-shape partition polytope is the convex hull of partition sums of all partitions that have a prescribed shape. A partition is separable if the convex hull of its parts are pairwise disjoint. The separability of a partition is a necessary condition for the associated partition sum to be a vertex of the single-shape partition polytope. It is also a sufficient condition for d=1 or p=2. However, the sufficiency fails to hold for d≥3 and p≥3. In this paper, we give some geometric sufficient conditions as well as some necessary conditions of vertices in general d and p. Thus, the open case for d=2 and p≥3 is resolved.     

A rooted-forest partition with uniform vertex demand

A rooted-forest is the union of vertex-disjoint rooted-trees. Suppose we are given a graph G=(V,E), a collection {R ₁,??,R _k } of k root-sets (i.e., vertex-sets), and a positive integer d. We prove a necessary and sufficient condition for G to contain k edge-disjoint rooted-forests F ₁,??,F _k with root-sets R ₁,??,R _k such that each vertex is spanned by exactly d of F ₁,??,F _k .     

The adjacent vertex distinguishing total coloring of planar graphs

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices have distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing total coloring of G is denoted by $\chi''_{a}(G)$ . In this paper, we characterize completely the adjacent vertex distinguishing total chromatic number of planar graphs G with large maximum degree Δ by showing that if Δ≥14, then $\varDelta+1\leq \chi''_{a}(G)\leq \varDelta+2$ , and $\chi''_{a}(G)=\varDelta+2$ if and only if G contains two adjacent vertices of maximum degree.     

Perfect matchings in paired domination vertex critical graphs

A vertex subset S of a graph G=(V,E) is a paired dominating set if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The paired domination number of G, denoted by γ _pr (G), is the minimum cardinality of a paired dominating set of?G. A?graph with no isolated vertex is called paired domination vertex critical, or briefly γ _pr -critical, if for any vertex v of G that is not adjacent to any vertex of degree one, γ _pr (G?v)<γ _pr (G). A?γ _pr -critical graph G is said to be k-γ _pr -critical if γ _pr (G)=k. In this paper, we firstly show that every 4-γ _pr -critical graph of even order has a perfect matching if it is K _1,5-free and every 4-γ _pr -critical graph of odd order is factor-critical if it is K _1,5-free. Secondly, we show that every 6-γ _pr -critical graph of even order has a perfect matching if it is K _1,4-free.     

Dynamic matchings in left vertex weighted convex bipartite graphs

A left vertex weighted convex bipartite graph (LWCBG) is a bipartite graph \(G=(X,Y,E)\) in which the neighbors of each \(x\in X\) form an interval in \(Y\) where \(Y\) is linearly ordered, and each \(x\in X\) has an associated weight. This paper considers the problem of maintaining a maximum weight matching in a dynamic LWCBG. The graph is subject to the updates of vertex and edge insertions and deletions. Our dynamic algorithms maintain the update operations in \(O(\log ^2{|V|})\) amortized time per update, obtain the matching status of a vertex (whether it is matched) in constant worst-case time, and find the pair of a matched vertex (with which it is matched) in worst-case \(O(k)\) time, where \(k\) is not greater than the cardinality of the maximum weight matching. That achieves the same time bound as the best known solution for the problem of the unweighted version.     

The vertex cover game: Application to transport networks

As communications are progressing, transport networks need to be monitored, more specifically, camera surveillance of violations is needed. Standards are being developed on how to install cameras, and the question of efficiently distributing surveillance devices across the road network ensue. This task is addressed in this paper by using the methods of the cooperative game theory. The vertex cover game is introduced, and its properties are studied. Since surveillance cameras are to cover all areas of the network, the characteristic function depends on the vertex covers of the graph. The Shapley–Shubik index is used as the measure of centrality. The Shapley–Shubik index is shown to be efficient in a vertex cover game for the allocation of cameras in a transport network. Proceeding from the Shapley–Shubik indices calculated in this study, recommendations were given for the allocation of surveillance cameras in a specific transport network in a district of the City of Petrozavodsk, Russia.     

Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree

An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge coloring of G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring of G is denoted by χ′ _a (G). Let mad(G)\mathop{\mathrm{mad}}(G) and Δ denote the maximum average degree and the maximum degree of a graph G, respectively.