Search

We show that for each k ≥ 4 and n > r ≥ k + 1 , every n -vertex hypergraph with edge sizes at least r and no Berge cycle of length at least k has at most (k − 1) (n − 1) r edges. The bound is exact, and we describe the extremal hypergraphs. This implies and slightly refines the theorem of Győri, Katona and Lemons that for n > r ≥ k ≥ 3 , every n -vertex r -uniform hypergraph with no Berge path of length k has at most (k − 1) n r + 1 edges. To obtain the bounds, we study bipartite graphs with no cycles of length at least 2 k , and then translate the results into the language of multi-hypergraphs. [ABSTRACT FROM AUTHOR]

Fractional revival is a quantum transport phenomenon important for entanglement generation in spin networks. This takes place whenever a continuous-time quantum walk maps the characteristic vector of a vertex to a superposition of the characteristic vectors of a subset of vertices containing the initial vertex. A main focus will be on the case when the subset has two vertices. We explore necessary and sufficient spectral conditions for graphs to exhibit fractional revival. This provides a characterization of fractional revival in paths and cycles. Our work builds upon the algebraic machinery developed for related quantum transport phenomena such as state transfer and mixing, and it reveals a fundamental connection between them. [ABSTRACT FROM AUTHOR]

The n -dimensional balanced hypercube B H n (n ≥ 1) has been proved to be a bipartite graph. Let P be a set of edges in B H n. For any two vertices u , v from different partite sets of V (B H n). In this paper, we prove that if | P | ≤ 2 n − 2 and the subgraph induced by P has neither u nor v as internal vertices , or both of u and v as end-vertices, then B H n contains a Hamiltonian path joining u and v passing through every edge of P if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths. As a corollary, if | P | ≤ 2 n − 1 , then B H n contains a Hamiltonian cycle passing through every edge of P if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths. [ABSTRACT FROM AUTHOR]

A star edge-coloring of a graph G is a proper edge-coloring without 2-colored paths and cycles of length 4. For a graph G , let the list star chromatic index of G be the minimum k such that for any k -uniform list assignment L for the set of edges, G has a star edge-coloring from L. In this paper we prove that the list star chromatic index of every k -degenerate graph G with maximum degree Δ is at most (3 k − 2) Δ − k 2 + 2. For K 4 -minor free graphs (k = 2), we decrease this bound to 3 Δ − 3 , Δ ≥ 3. We do not use the discharging method but rather we use the fundamental structural properties of k -degenerate graphs and K 4 -minor free graphs. [ABSTRACT FROM AUTHOR]

Let P k be a path, C k a cycle on k vertices, and K k , k a complete bipartite graph with k vertices on each side of the bipartition. We prove that (1) for any integers k , t > 0 and a graph H there are finitely many subgraph minimal graphs with no induced P k and K t , t that are not H -colorable and (2) for any integer k > 4 there are finitely many subgraph minimal graphs with no induced P k that are not C k − 2 -colorable. The former generalizes the result of Hell and Huang (2013) and the latter extends a result of Bruce etal. (2009). Both our results lead to polynomial-time certifying algorithms for the corresponding coloring problems. [ABSTRACT FROM AUTHOR]

Abstract Given a fixed graph H , we provide a sharp degree-sum condition such that if a graph G is sufficiently large with sufficiently large minimum degree sum, then it contains a spanning H -subdivision in which the ground vertices and lengths of the corresponding edge paths are specified. [ABSTRACT FROM AUTHOR]

Abstract We study a facility location problem motivated by requirements pertaining to the distribution of charging stations for electric vehicles: Place a minimum number of battery charging stations at a subset of nodes of a network, so that battery-powered electric vehicles will be able to move between destinations using " t -spanning" routes, of lengths within a factor t > 1 of the length of a shortest path, while having sufficient charging stations along the way. We give constant-factor approximation algorithms for minimizing the number of charging stations, subject to the t -spanning constraint. We study two versions of the problem, one in which the stations are required to support a single ride (to a single destination), and one in which the stations are to support multiple rides through a sequence of destinations, where the destinations are revealed one at a time. [ABSTRACT FROM AUTHOR]

Abstract For graphs G and H , let G → H signify that any red/blue edge coloring of G contains a monochromatic H as a subgraph. Let G (K k (n) , p) be random graph spaces with edge probability p , where K k (n) is the complete k -partite graph with n vertices in each part. It is shown that if n p → ∞ , then Pr [ G (K k (n) , p) → P (k − 1 − o (1)) n ] → 1 for k = 2 , 3. [ABSTRACT FROM AUTHOR]

Abstract This paper presents an efficient method for constructing 2 2 n − 2 cyclic different de Bruijn sequences of order 2 n from the feedback function of a de Bruijn sequence of order n. This is done by extending an n -stage nonlinear feedback shift register (NFSR) to a 2 n -stage NFSR, and then recursively joining all cycles of the 2 n -stage NFSR to form a full cycle. [ABSTRACT FROM AUTHOR]

Abstract Let D denote the distance matrix of a connected graph. The inertia of D is the triple of integers (n + (D) , n 0 (D) , n − (D)) , where n + (D) , n 0 (D) , n − (D) denote the number of positive, 0, and negative eigenvalues of D , respectively. The D -energy is the sum of the absolute eigenvalues of D. In this paper, we first obtain the inertia and a formula for the determinant of the distance matrices of the line graphs of unicyclic graphs; Then, as applications, we obtain the graphs with maximum (resp. minimum) D -energy among all these graphs. [ABSTRACT FROM AUTHOR]

Abstract In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph G is defined as the sum of the absolute values of the zeros of the matching polynomial of G. In this paper, we first present some new techniques of comparing the matching energies of two graphs. As the applications of these techniques, we can determine the unicyclic graphs of order n with the first to the eighth smallest matching energies for all n ≥ 42. [ABSTRACT FROM AUTHOR]

Abstract The signless Laplacian Estrada index of a graph G is defined as S L E E (G) = ∑ i = 1 n e q i , where q 1 , q 2 , ... , q n are the eigenvalues of the signless Laplacian matrix of G. A cactus is a connected graph in which any two cycles have at most one common vertex. In this paper, we characterize the unique graph with maximum S L E E among all cacti with n vertices and k cycles. Also, the unique graph with maximum S L E E among all cacti with n vertices and k cut edges is determined. [ABSTRACT FROM AUTHOR]

Abstract Let P k denote an induced path on k vertices. For k ≥ 5 , we show that the P k -free sandwich problem, partitioned probe problem, and unpartitioned probe problem are N P -complete. For k ≤ 4 , it is known that the P k -free sandwich problem, partitioned probe problem, and unpartitioned probe problem are in P. [ABSTRACT FROM AUTHOR]

An orientation of an undirected graph is obtained by assigning a direction to each of its edges. It is called cyclic when a directed cycle appears, and acyclic otherwise. We study efficient algorithms for enumerating the orientations of an undirected graph. To get the full picture, we consider both the cases of acyclic and cyclic orientations, under some rules specifying which nodes are the sources (i.e. their incident edges are all directed outwards). Our enumeration algorithms use linear space and provide new bounds for the delay, which is the maximum elapsed time between the output of any two consecutively listed solutions. We obtain a delay of O ( m ) for acyclic orientations and O ̃ ( m ) for cyclic ones. When just a single source is specified, these delays become O ( m ⋅ n ) and O ( m ⋅ h + h 3 ) , respectively, where h is the girth of the graph without the given source. When multiple sources are specified, the delays are the same as in the single source case. [ABSTRACT FROM AUTHOR]

Let D be a strongly connected balanced bipartite directed graph of order 2 a ≥ 8 . In this note we prove: (i). If D contains a cycle of length 2 a − 2 ≥ 6 and m a x { d ( x ) , d ( y ) } ≥ 2 a − 2 for every pair of vertices { x , y } with a common out-neighbour, then for every k , 1 ≤ k ≤ a − 1 , D contains a cycle of length 2 k . (ii). If D is not a directed cycle and m a x { d ( x ) , d ( y ) } ≥ 2 a − 1 for every pair of vertices { x , y } with a common out-neighbour, then for every k , 1 ≤ k ≤ a , D contains a cycle of length 2 k unless D is isomorphic to a certain digraph of order eight which we specify. [ABSTRACT FROM AUTHOR]

Let k and ℓ be integers satisfying 1 ≤ ℓ ≤ k ∕ 2 . An ℓ -offset Hamilton cycle C in a k -uniform hypergraph H on n vertices is a collection of edges of H such that for some cyclic order of [ n ] and every even i every pair of consecutive edges E i − 1 , E i in C (in the natural ordering of the edges) satisfies | E i − 1 ∩ E i | = ℓ and every pair of consecutive edges E i , E i + 1 in C satisfies | E i ∩ E i + 1 | = k − ℓ . We show that in general e k ℓ ! ( k − ℓ ) ! ∕ n k is the sharp threshold for the existence of the ℓ -offset Hamilton cycle in the random k -uniform hypergraph H n , p ( k ) . We also examine this structure’s natural connection to the 1–2–3 Conjecture. [ABSTRACT FROM AUTHOR]

Wu and Huang proposed a new variation of the hypercube, named balanced hypercube, which possesses many good properties such as bipanconnectivity, edge-bipancyclicity, Hamiltonian laceability, hyper Hamiltonian laceability. In this paper, we consider n -dimensional balanced hypercube with | F e | faulty edges and | F v | faulty vertices. We prove that if | F v | + | F e | ≤ n − 1 , then every fault-free edge of B H n lies on a fault-free cycle of every even length from 6 to 2 2 n − 2 | F v | , where n ≥ 2 ; and if | F v | + | F e | ≤ 2 n − 3 , then there is a fault-free cycle of every even length from 6 to 2 2 n − 2 | F v | in B H n , where n ≥ 2 . Furthermore, we propose the distance between vertex-disjoint edge e and cycle C , i.e., d ( e , C ) = m i n { d ( e , e ′ ) | e ′ ∈ E ( C ) } , where d ( e , e ′ ) = m i n { d ( u , x ) , d ( u , y ) , d ( v , x ) , d ( v , y ) | ( u , v ) = e , ( x , y ) = e ′ } . [ABSTRACT FROM AUTHOR]

The Wiener index W ( G ) of a connected graph G is defined to be the sum of distances between all pairs of vertices in G . In 1991, Šoltés studied changes of the Wiener index caused by removing a single vertex. He posed the problem of finding all graphs G so that equality W ( G ) = W ( G − v ) holds for all their vertices v . The cycle with 11 vertices is still the only known graph with this property. In this paper we study a relaxed version of this problem and find graphs which Wiener index does not change when a particular vertex v is removed. We show that there is a unicyclic graph G on n vertices with W ( G ) = W ( G − v ) if and only if n ≥ 9 . Also, there is a unicyclic graph G with a cycle of length c for which W ( G ) = W ( G − v ) if and only if c ≥ 5 . Moreover, we show that every graph G is an induced subgraph of H such that W ( H ) = W ( H − v ) . As our relaxed version is rich with solutions, it gives hope that Šoltes’s problem may have also some solutions distinct from C 11 . [ABSTRACT FROM AUTHOR]

Let C 1 and C 2 be two sets of cycles. We determine all generalised Ramsey numbers R ( C 1 , C 2 ) such that C 1 or C 2 contains a cycle of length at most 6. This generalises previous results of Erdős, Faudree, Rosta, Rousseau, and Schelp. Furthermore, we give a conjecture for the general case. We also provide a complete classification of most ( C 1 , C 2 ) -critical graphs such that C 1 or C 2 contains a cycle of length at most 5. For length 4, this is an easy extension of a recent result of Wu, Sun, and Radziszowski, in which | C 1 | = | C 2 | = 1 . For lengths 3 and 5, our results are new also in this special case. [ABSTRACT FROM AUTHOR]

A star-edge coloring of a graph G is a proper edge coloring such that every 2-colored connected subgraph of G is a path of length at most 3. For a graph G , let the list star chromatic index of G , c h s ′ ( G ) , be the minimum k such that for any k -uniform list assignment L for the set of edges, G has a star-edge coloring from L . Dvořák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we give a partial answer to the question of Dvořák et al. (2013) by proving that if the maximum average degree of a subcubic graph G is less than 30 11 then c h s ′ ( G ) ≤ 7 . We consider also graphs with any maximum degree, we proved that if the maximum average degree of a graph G is less than 7 3 (resp., 5 2 , 8 3 ), then c h s ′ ( G ) ≤ 2 Δ ( G ) − 1 (resp., c h s ′ ( G ) ≤ 2 Δ ( G ) , c h s ′ ( G ) ≤ 2 Δ ( G ) + 1 ). [ABSTRACT FROM AUTHOR]

An arc-coloured digraph is strongly rainbow connected if for every pair of vertices ( u , v ) there exists a shortest path from u to v all of whose arcs have different colours. The strong rainbow connection number of a digraph is the minimum number of colours needed to make the graph strongly rainbow connected. In this paper, we study the strong rainbow connection number of minimally strongly connected digraphs, non-Hamiltonian strong digraphs and strong tournaments. [ABSTRACT FROM AUTHOR]

We study a game played on a graph by two players, named Maximizer and Minimizer. Each round two new vertices are chosen; first Maximizer chooses a vertex u that has at least one unchosen neighbor and then Minimizer chooses a neighbor of u . This process eventually produces a maximal matching of the graph. Maximizer tries to maximize the number of edges chosen, while Minimizer tries to minimize it. The matcher number α g ′ ( G ) of a graph G is the number of edges chosen when both players play optimally. In this paper it is proved that α g ′ ( G ) ≥ 2 3 α ′ ( G ) , where α ′ ( G ) denotes the matching number of graph G , and this bound is tight. Further, if G is bipartite, then α g ′ ( G ) = α ′ ( G ) . We also provide some results on graphs of large odd girth and on dense graphs. [ABSTRACT FROM AUTHOR]

A graph G of order n satisfies the cut condition (CC) if there are at least | A | edges between any set A ⊂ V ( G ) , | A | ≤ n ∕ 2 , and its complement A ¯ = V ( G ) ∖ A . For even n , G satisfies the even cut condition (ECC), if [ A , A ¯ ] contains at least n ∕ 2 edges, for every A ⊂ V ( G ) , | A | = n ∕ 2 . We investigate here the minimum number of edges in a graph G satisfying CC or ECC. A simple counting argument shows that for both cut conditions | E ( G ) | ≥ n − 1 , and the star K 1 , n − 1 is extremal. Faudree et al. (1999) conjectured that the extremal graphs with maximum degree Δ ( G ) < n − 1 satisfying ECC have 3 n ∕ 2 − O ( 1 ) edges. Here we prove the tight bound | E ( G ) | ≥ 3 n ∕ 2 − 3 , for every graph G with Δ ( G ) < n − 1 and satisfying CC. If G is 2-connected and satisfies ECC, we prove that | E ( G ) | ≥ 3 n ∕ 2 − 2 holds and tight, for every even n . We obtain the weaker bound | E ( G ) | ≥ 5 n ∕ 4 − 2 , for every graph of order n ≡ 0 ( mod 4 ) with Δ ( G ) < n − 1 and satisfying ECC; meanwhile we conjecture that | E ( G ) | ≥ 3 n ∕ 2 − 4 holds, for every even n . [ABSTRACT FROM AUTHOR]

A k -coloring of a graph G = ( V , E ) is called semi-equitable if there exists a partition of its vertex set into independent subsets V 1 , … , V k in such a way that | V 1 | ⁄ ∈ { ⌈ | V | ∕ k ⌉ , ⌊ | V | ∕ k ⌋ } and ‖ V i | − | V j ‖ ≤ 1 for each i , j = 2 , … , k . The color class V 1 is called non-equitable. In this note we consider the complexity of semi-equitable k -coloring, k ≥ 4 , of the vertices of a cubic or subcubic graph G . In particular, we show that, given a n -vertex subcubic graph G and constants ϵ > 0 , k ≥ 4 , it is NP-complete to obtain a semi-equitable k -coloring of G whose non-equitable color class is of size s if s ≥ n ∕ 3 + ϵ n , and it is polynomially solvable if s ≤ n ∕ 3 . [ABSTRACT FROM AUTHOR]

The n-sum graph Negami’s splitting formula for the Tutte polynomial is not valid in the region ( x − 1 ) ( y − 1 ) = q for q = 1 , 2 , … n − 1 with the additional region y = 1 if n > 3 . This region corresponds to (up to prefactors and change of variables) the Ising model, the q -state Potts model, the number of spanning forest generator and particularizations of these. We show splitting formulas for these specializations. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new convexity on graphs similar to the well known P 3 -convexity, which we will call P 3 ∗ -convexity. We show that several P 3 ∗ -convexity parameters (hull number, convexity number, Carathéodory number, Radon number, interval number and percolation time) are NP-hard even on bipartite graphs. We prove a strong relationship between this convexity and the well known geodesic convexity, which implies several NP-hardness results for the latter. In order to show that, we prove that the hull number for the P 3 -convexity is NP-hard even for subgraphs of grids and that the convexity number for the P 3 -convexity is NP-hard even for bipartite graphs with diameter 3. We also obtain linear time algorithms to determine those parameters for the above mentioned convexities for cographs and P 4 -sparse graphs. [ABSTRACT FROM AUTHOR]

In this paper a new parameter for hypergraphs called hypergraph infection is defined. This concept generalizes zero forcing in graphs to hypergraphs. The exact value of the infection number of complete and complete bipartite hypergraphs is determined. A formula for the infection number for interval hypergraphs and several families of cyclic hypergraphs is given. The value of the infection number for a hypergraph whose edges form a symmetric t -design is given, and bounds are determined for a hypergraph whose edges are a t -design. Finally, the infection numbers for several hypergraph products and line graphs are considered. [ABSTRACT FROM AUTHOR]

Let χ Σ t ( G ) and χ Σ l t ( G ) be the neighbor sum distinguishing total chromatic and total choice numbers of a graph G , respectively. In this paper, we present some new upper bounds of χ Σ l t ( G ) for ℓ -degenerate graphs with integer ℓ ≥ 1 , and of χ Σ t ( G ) for 2-degenerate graphs. As applications of these results, (i) for a general graph G , χ Σ t ( G ) ≤ χ Σ l t ( G ) ≤ max { Δ ( G ) + ⌊ 3 col ( G ) 2 ⌋ − 1 , 3 col ( G ) − 2 } , where col ( G ) is the coloring number of G ; (ii) for a 2-degenerate graph G , we determine the exact value of χ Σ t ( G ) if Δ ( G ) ≥ 6 and show that χ Σ t ( G ) ≤ 7 if Δ ( G ) ≤ 5 . [ABSTRACT FROM AUTHOR]

For a finite, simple, undirected graph G with a vertex weight function, the Maximum Weight Independent Set (MWIS) problem asks for an independent vertex set of G with maximum weight. MWIS is a well-known NP-hard problem of fundamental importance. For claw-free graphs, MWIS can be solved in polynomial time—in 1980, the first two such algorithms were independently found by Minty for MWIS and by Sbihi for the unweighted case. For a constant ℓ ≥ 2 , let ℓ G denote the disjoint union of ℓ copies of G . In this paper, using a dynamic programming approach (inspired by Farber’s result about MWIS for 2 K 2 -free graphs), we show that for any fixed ℓ , MWIS can be solved in polynomial time for ℓ claw-free graphs. This solves the open cases for MWIS on ( P 3 + claw)-free graphs and on ( 2 K 2 + claw)-free graphs and extends known results for claw-free graphs, ℓ K 2 -free graphs, ( K 2 + claw)-free graphs, and ℓ P 3 -free graphs. [ABSTRACT FROM AUTHOR]

For a graph G = ( V , E ) , a subset F ⊂ V ( G ) is called an R k -vertex-cut of G if G − F is disconnected and each vertex u ∈ V ( G ) − F has at least k neighbors in G − F . The R k -vertex-connectivity of G , denoted by κ k ( G ) , is the cardinality of the minimum R k -vertex-cut of G , which is a refined measure for the fault tolerance of network G . In this paper, we study κ 2 for Cayley graphs generated by k -trees. Let S y m ( n ) be the symmetric group on { 1 , 2 , … , n } and T be a set of transpositions of S y m ( n ) . Let G ( T ) be the graph on n vertices { 1 , 2 , . . . , n } such that there is an edge i j in G ( T ) if and only if the transposition i j ∈ T . The graph G ( T ) is called the transposition generating graph of T . We denote by C a y ( S y m ( n ) , T ) the Cayley graph generated by G ( T ) . The Cayley graph C a y ( S y m ( n ) , T ) is denoted by T k G n if G ( T ) is a k -tree. We determine κ 2 ( T k G n ) in this work. The trees are 1-trees, and the complete graph on n vertices is a n − 1 -tree. Thus, in this sense, this work is a generalization of the results on Cayley graphs generated by transposition generating trees (Yang et al., 2010) and the complete-transposition graphs (Wang et al., 2015). [ABSTRACT FROM AUTHOR]

A facial unique-maximum coloring of a plane graph is a vertex coloring where on each face α the maximal color appears exactly once on the vertices of α . If the coloring is required to be proper, then the upper bound for the minimal number of colors required for such a coloring is set to 5. Fabrici and Göring (2016) even conjectured that 4 colors always suffice. Confirming the conjecture would hence give a considerable strengthening of the Four Color Theorem. In this paper, we prove that the conjecture holds for subcubic plane graphs, outerplane graphs and plane quadrangulations. Additionally, we consider the facial edge-coloring analogue of the aforementioned coloring and prove that every 2-connected plane graph admits such a coloring with at most 4 colors. [ABSTRACT FROM AUTHOR]

For two positive integers k , r , a ( k , r ) -coloring (or r -hued k -coloring) of a graph G is a proper k -vertex-coloring such that every vertex v of degree d G ( v ) is adjacent to at least min { d G ( v ) , r } distinct colors. The r -hued chromatic number, χ r ( G ) , is the smallest integer k for which G has a ( k , r ) -coloring. The maximum average degree of G , denoted by mad ( G ) , equals max { 2 | E ( H ) | ∕ | V ( H ) | : H is a subgraph of G } . In this paper, we prove the following results using the well-known discharging method. For a graph G , if mad ( G ) < 12 5 , then χ 3 ( G ) ≤ 6 ; if mad ( G ) < 7 3 , then χ 3 ( G ) ≤ 5 ; if G has no C 5 -components and mad ( G ) < 8 3 , then χ 2 ( G ) ≤ 4 . [ABSTRACT FROM AUTHOR]

For a nondecreasing sequence of integers S = ( s 1 , s 2 , … ) an S -packing k -coloring of a graph G is a mapping from V ( G ) to { 1 , 2 , … , k } such that vertices with color i ∈ { 1 , 2 , … , k } have pairwise distance greater than s i . A natural restriction of this concept obtained by setting s i = d + ⌊ i − 1 n ⌋ is called a ( d , n ) -packing coloring of a graph G . The smallest integer k for which there exists a ( d , n ) -packing coloring of G is called the ( d , n ) -packing chromatic number of G . We study ( d , n ) -packing chromatic colorings of several lattices including the infinite square, hexagonal, triangular, eight-regular, octagonal and two-row square lattice. [ABSTRACT FROM AUTHOR]

A signed graph G is a graph associated with a mapping σ : E ( G ) → { + 1 , − 1 } . An edge e ∈ E ( G ) is positive if σ ( e ) = 1 and negative if σ ( e ) = − 1 . A circuit in G is balanced if it contains an even number of negative edges, and unbalanced otherwise. A barbell consists of two unbalanced circuits joined by a path. A signed circuit of G is either a balanced circuit or a barbell. A signed graph is coverable if each edge is contained in some signed circuit. An oriented signed graph (bidirected graph) has a nowhere-zero integer flow if and only if it is coverable. A signed circuit cover of G is a collection F of signed circuits in G such that each edge e ∈ E ( G ) is contained in at least one signed circuit of F ; The length of F is the sum of the lengths of the signed circuits in it. The minimum length of a signed circuit cover of G is denoted by s c c ( G ) . The first nontrivial bound on s c c ( G ) was established by Máčajová et al., who proved that s c c ( G ) ≤ 11 | E ( G ) | for every coverable signed graph G , which was recently improved by Cheng et al. to s c c ( G ) ≤ 14 3 | E ( G ) | . In this paper, we prove that s c c ( G ) ≤ 25 6 | E ( G ) | for every coverable signed graph G . [ABSTRACT FROM AUTHOR]

The Wiener index W ( G ) of a connected graph G is the sum of distances between all pairs of vertices of G . A connected graph G is said to be a cactus if each of its blocks is either a cycle or an edge. Let G n , t be the set of all n -vertex cacti containing exactly t cycles. Liu and Lu (2007) determined the unique graph in G n , t with the minimum Wiener index. We now establish a sharp upper bound on the Wiener index of graphs in G n , t and identify the corresponding extremal graphs. [ABSTRACT FROM AUTHOR]

In 1975, P. Erdös proposed the problem of determining the maximum number f ( n ) of edges in a graph with n vertices in which any two cycles are of different lengths. In this paper, it is proved that f ( n ) ≥ n + 107 3 t + 7 3 for t = 1260 r + 169 ( r ≥ 1 ) and n ≥ 2119 4 t 2 + 87978 t + 15957 4 . Consequently, lim inf n → ∞ f ( n ) − n n ≥ 2 + 7654 19071 , which is better than the previous bounds 2 (Shi, 1988), 2 . 4 (Lai, 2003). The conjecture lim n → ∞ f ( n ) − n n = 2 . 4 is not true. [ABSTRACT FROM AUTHOR]

We address the problem of computing distances between permutations that take into account similarities between elements of the ground set dictated by a graph. The problem may be summarized as follows: Given two permutations and a positive cost function on transpositions that depends on the similarity of the elements involved, find a smallest cost sequence of transpositions that converts one permutation into another. Our focus is on costs that may be described via special metric-tree structures. The presented results include a linear-time algorithm for finding a minimum cost decomposition for simple cycles and a linear-time 4 ∕ 3 -approximation algorithm for permutations that contain multiple cycles. The proposed methods rely on investigating a newly introduced balancing property of cycles embedded in trees, cycle-merging methods, and shortest path optimization techniques. [ABSTRACT FROM AUTHOR]

We introduce a variant of the vertex-distinguishing edge coloring problem, where each edge is assigned a subset of colors. The label of a vertex is the union of the sets of colors on edges incident to it. In this paper we investigate the problem of finding a coloring with the minimum number of colors where every vertex receives a distinct label. Finding such a coloring generalizes several other well-known problems of vertex-distinguishing colorings in graphs. We show that for any graph (without connected component reduced to an edge or a single vertex), the minimum number of colors for which such a coloring exists can only take 3 possible values depending on the order of the graph. Moreover, we provide the exact value for paths, cycles and complete binary trees. [ABSTRACT FROM AUTHOR]

Given an arbitrary directed graph G = ( V , E ) with non-negative edge lengths, we present an algorithm that computes all pairs shortest paths in time O ( m ∗ n + m lg n + n T ψ ( m ∗ , n ) ) , where m ∗ is the number of different edges contained in shortest paths and T ψ ( m ∗ , n ) is the running time of an algorithm ψ solving the single-source shortest path problem (SSSP). This is a substantial improvement over a trivial n times application of ψ that runs in O ( n T ψ ( m , n ) ) . In our algorithm we use ψ as a black box and hence any improvement on ψ results also in improvement of our algorithm. A combination of our method, Johnson’s reweighting technique and topological sorting results in an O ( m ∗ n + m lg n ) all-pairs shortest path algorithm for directed acyclic graphs with arbitrary edge lengths. We also point out a connection between the complexity of a certain sorting problem defined on shortest paths and SSSP. Finally, we show how to improve the performance of the proposed algorithm in practice. We then empirically measure the running times of various all-pairs shortest path algorithms on randomly generated graph instances and obtain very promising results. [ABSTRACT FROM AUTHOR]

A rerouting sequence is a sequence of shortest s t -paths such that consecutive paths differ in one vertex. We study the Shortest Path Rerouting Problem, which asks, given two shortest s t -paths P and Q in a graph G , whether a rerouting sequence exists from P to Q . This problem is PSPACE-hard in general, but we show that it can be solved in polynomial time if G is planar. In addition, it can be solved in polynomial time when every vertex has at most two neighbors closer to s and at most two neighbors closer to t . To this end, we introduce a dynamic programming method for reconfiguration problems, based on using small encodings of reconfiguration graphs. [ABSTRACT FROM AUTHOR]

This paper considers distributed storage systems (DSSs) from a graph theoretic perspective. A DSS is constructed by means of the path decomposition of a 3 -regular graph into P 4 paths. The paths represent the disks of the DSS and the edges of the graph act as the blocks of storage. We deduce the properties of the DSS from a related graph and show their optimality. [ABSTRACT FROM AUTHOR]

The first multiplicative Zagreb index of a graph G is the product of the square of every vertex degree, while the second multiplicative Zagreb index is the product of the products of degrees of pairs of adjacent vertices. In this paper, we explore the trees in terms of given number of vertices of maximum degree. The maximum and minimum values of ∏ 1 ( G ) and ∏ 2 ( G ) of trees with arbitrary number of maximum degree are provided. In addition, the corresponding extremal graphs are characterized. [ABSTRACT FROM AUTHOR]

The center function on a connected graph G has as input a sequence of vertices of G . The output is the set of vertices that minimize the maximum distance to the entries of the input. If the input is a sequence containing each vertex of G once, then the output is just the classical center of G . This paper studies the center function from the viewpoint of consensus theory. We present consensus axioms that are satisfied by the center function on all connected graphs. Next, we study classes of graphs on which the center function is characterized by such ‘universal’ axioms only. We present two instances: the graphs with a dominating vertex (that is, a vertex adjacent to all other vertices), and the paths. Trees in general do not fall into this category. But we show that trees with diameter at most five have such a characterization. Our approach is to highlight unexpected analogies between the center function and the median function. [ABSTRACT FROM AUTHOR]

A Nordhaus–Gaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In Henning et al. (2011) the authors (Henning et al.) show that if G 1 ⊕ G 2 = K ( s , s ) , and neither G 1 nor G 2 has isolated vertices, then the product γ t ( G 1 ) γ t ( G 2 ) is at most max { 8 s , ⌊ ( s + 6 ) 2 ∕ 4 ⌋ } , where γ t is the total domination number. In this paper we will use a vertex disjoint star covering technique, to significantly improve the mentioned bound. In particular, we will show that if G 1 ⊕ G 2 = K ( s , s ) , and neither G 1 nor G 2 has isolated vertices, then γ t ( G 1 ) γ t ( G 2 ) ≤ max { 8 s , ⌊ ( s + 5 ) 2 ∕ 4 ⌋ } . [ABSTRACT FROM AUTHOR]

Let q ( G ) and μ ( G ) denote the signless Laplacian and distance signless Laplacian spectral radius of a digraph G , respectively. In this paper, we characterize the extremal digraph which has the maximum signless Laplacian spectral radius among all strongly connected digraphs with given dichromatic number. We also determine the extremal digraph having the minimum distance signless Laplacian spectral radius among all strongly connected digraphs with given vertex connectivity. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a graph on n vertices and f : V → [ 1 , n ] a one to one map of V onto the integers 1 through n . Let d i l a t i o n ( f ) = max { | f ( v ) − f ( w ) | : v w ∈ E } . Define the bandwidth B ( G ) of G to be the minimum possible value of d i l a t i o n ( f ) over all such one to one maps f . Next define the Kneser Graph K ( n , r ) to be the graph with vertex set [ n ] r , the collection of r -subsets of an n element set, and edge set E = { A B : A , B ∈ [ n ] r , A ∩ B = ∅ } . For fixed r ≥ 4 and n growing we show that B ( K ( n , r ) ) = n − 1 r + 1 2 n − 4 r − 1 − 1 2 n − 1 r − 2 + O ( n r − 4 ) . [ABSTRACT FROM AUTHOR]

The present paper is devoted to estimating effective resistances in large weighted undirected Cayley graph Cay ( S n , T n ) on symmetric group S n . We obtain asymptotically exact bounds for minimal resistances in Cay ( S n , T n ) . Maximal and average resistances in Cayley graphs on symmetric groups are given in terms of degree, girth and spectral gap. Sharp asymptotic bounds for maximal and average resistances are obtained for star and transposition Cayley graphs. Finally, we find improved estimates of effective resistances in bubble-sort Cayley graphs. [ABSTRACT FROM AUTHOR]

This paper deals with open shops subject to the constraint that some conflicting jobs cannot be processed simultaneously on different machines. In the context of our study, these conflicts are given by an undirected graph, called the conflict graph. We seek a schedule that minimizes the maximum completion time (makespan). We first prove the NP-hardness of different versions of this problem. Then, we present polynomial-time solvable cases, for which we devise simple and efficient algorithms. On the other hand, we present heuristics and lower bounds for the general case. The heuristics are based on the construction of matchings in bipartite graphs as well as on a specific insertion technique combined with beam search. Finally, we test the efficiency of the heuristics and report our computational experiments that display satisfying results. [ABSTRACT FROM AUTHOR]

A graph G is said to be quasi- λ -distance-balanced if for every pair of adjacent vertices u and v , the number of vertices that are closer to u than to v is λ times bigger (or λ times smaller) than the number of vertices that are closer to v than to u , for some positive rational number λ > 1 . This paper introduces the concept of quasi- λ -distance-balanced graphs, and gives some interesting examples and constructions. It is proved that every quasi- λ -distance-balanced graph is triangle-free. It is also proved that the only quasi- λ -distance-balanced graphs of diameter two are complete bipartite graphs. In addition, quasi- λ -distance-balanced Cartesian and lexicographic products of graphs are characterized. Connections between symmetry properties of graphs and the metric property of being quasi- λ -distance-balanced are investigated. Several open problems are posed. [ABSTRACT FROM AUTHOR]

We consider boolean linear programming formulations of the independent set, the vertex and the edge dominating set problems and prove their polynomial-time solvability for classes of graphs with (augmented) constraint matrices having bounded minors in the absolute value. [ABSTRACT FROM AUTHOR]