首页期刊导航|Discrete Applied Mathematics
期刊信息/Journal information
Discrete Applied Mathematics
North-Holland
Discrete Applied Mathematics

North-Holland

0166-218X

Discrete Applied Mathematics/Journal Discrete Applied MathematicsSCIAHCIISTPEI
正式出版
收录年代

    A new lower bound on graph gonality

    Harp M.Jackson E.Jensen D.Speeter N....
    8页
    查看更多>>摘要：? 2021 Elsevier B.V.We define a new graph invariant called the scramble number. We show that the scramble number of a graph is a lower bound for the gonality and an upper bound for the treewidth. Unlike the treewidth, the scramble number is not minor monotone, but it is subgraph monotone and invariant under subdivision. We compute the scramble number and gonality of several families of graphs for which these invariants are strictly greater than the treewidth.
      原文链接:
    • NSTL
    • Elsevier

    On the eccentric connectivity index of uniform hypergraphs

    Weng W.Zhou B.
    14页
    查看更多>>摘要：? 2021 Elsevier B.V.The eccentric connectivity index of a connected hypergraph G with vertex set V(G) is defined as ξc(G)=∑u∈V(G)duηu, where du denotes the degree of u and ηu denotes the eccentricity of u in G. We propose some hypergraph transformations that increase or decrease the eccentric connectivity index of a uniform hypergraph. We determine the unique k-uniform hypertrees with the first two largest eccentric connectivity indices, as well as the unique k-uniform hypertrees with the first three smallest eccentric connectivity indices among k-uniform hypertrees with fixed number of edges. We determine the unique hypertrees with the largest and the smallest eccentric connectivity indices respectively among k-uniform hypertrees with fixed number of edges and fixed diameter. We determine the unique hypertrees with the largest eccentric connectivity index among k-uniform hypertrees with fixed number of edges and fixed maximum degree. We also determine the unique hypergraphs with the largest and the smallest eccentric connectivity indices respectively among k-uniform unicyclic hypergraphs with fixed number of edges.
      原文链接:
    • NSTL
    • Elsevier

    Two-to-one functions from Galois extensions

    Bartoli D.Giulietti M.Timpanella M.
    8页
    查看更多>>摘要：? 2021 Elsevier B.V.Recently, two-to-one mappings have received a lot of attention due to their applications to cryptography and to the construction of classes of cryptographic functions. In this paper, we propose a new method to obtain m-to-1 functions based on Galois groups of rational functions. We feel that such an approach might be the starting point of a new line of research in the area of m-to-1 mappings.
      原文链接:
    • NSTL
    • Elsevier

    Localization game for random graphs

    Dudek A.English S.Frieze A.MacRury C....
    13页
    查看更多>>摘要：? 2021 Elsevier B.V.We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The minimum number of probes necessary per round to locate the robber on a given graph G is the localization number ζ(G). In this paper, we improve the bounds for dense random graphs determining the asymptotic behaviour of ζ(G). Moreover, we extend the argument to sparse graphs.
      原文链接:
    • NSTL
    • Elsevier

    Letter graphs and modular decomposition

    Ferguson R.Vatter V.
    6页
    查看更多>>摘要：? 2021 Elsevier B.V.We prove that if the prime graphs in a graph class have bounded lettericity, then the entire class has bounded lettericity if and only if it does not contain arbitrary large matchings, co-matchings, or a family of graphs that we call stacked paths.
      原文链接:
    • NSTL
    • Elsevier

    On the number of minimal codewords in codes generated by the adjacency matrix of a graph

    Kurz S.
    8页
    查看更多>>摘要：? 2021Minimal codewords have applications in decoding linear codes and in cryptography. We study the number of minimal codewords in binary linear codes that arise by appending a unit matrix to the adjacency matrix of a graph.
      原文链接:
    • NSTL
    • Elsevier

    The minimum degree Group Steiner problem

    Kortsarz G.Nutov Z.
    11页
    查看更多>>摘要：? 2021The DB-GST problem is given an undirected graph G(V,E), and a collection of groups S={Si}i=1q,Si?V, find a tree that contains at least one vertex from every group Si, so that the maximum degree is minimal. This problem was motivated by On-Line algorithms Hajiaghayi (2016), and has applications in VLSI design and fast Broadcasting. In the WDB-GST problem, every vertex v has individual degree bound dv, and every e∈E has a cost c(e)>0. The goal is, to find a tree that contains at least one terminal from every group, so that for every v, degT(v)≤dv, and among such trees, find the one with minimum cost. We give the first approximation for this problem, an (O(log2n),O(log2n)) bicriteria approximation ratio the WDB-GST problem on trees inputs. This implies an O(log2n) approximation for DB-GST on tree inputs. The previously best known ratio for the WDB-GST problem on trees was a bicriterion (O(log2n),O(log3n)) (the approximation for the degrees is O(log3n)) ratio which is folklore. Getting O(log2n) approximation requires careful case analysis and was not known. Our result for WDB-GST generalizes the classic result of Garg et al. (2016) that approximated the cost within O(log2n), but did not approximate the degree. Our main result is an O(log3n) approximation for BD-GST on Bounded Treewidth graphs. The DB-Steiner k-tree problem is given an undirected graph G(V,E), a collection of terminals S?V, and a number k, find a tree T(V′,E′) that contains at least k terminals, of minimum maximum degree. We prove that if the DB-GST problem admits a ρ ratio approximation, then the DB-Steiner k-tree problem, admits an O(log2k?ρ) expected approximation. We also show that if there are k groups, there exists an algorithm that is able to coverk/4 of the groups with minimum maximal degree, then there is a deterministic O(logn?ρ) approximation for DB-Steiner k-tree problem. Using the work of Guo et al. (2020) we derive an O(log3n) approximation for DB-Steiner k-tree problem on general graphs, that runs in quasi-polynomial time.
      原文链接:
    • NSTL
    • Elsevier

    Strong cuts from compatibility relations for the Dial-a-Ride Problem

    Morapitiye S.Kis T.
    18页
    查看更多>>摘要：? 2021 Elsevier B.V.In this paper we study the Dial-a-Ride Problem, which is a variant of the well-studied Vehicle Routing Problem, where a fleet of vehicles has to satisfy a set of transportation requests between given pickup and delivery locations, and the solution is a set of routes satisfying several constraints, and minimizing the transportation costs. Our main goal is to investigate the classes of valid inequalities that can be obtained from the compatibility relation on the arcs. The compatibility relations are derived from the constraints of the problem, such as precedence relations, time windows and the capacity of the vehicles, and their main use is to exclude infeasible vehicle paths. We strengthen the lifting for an existing class of cuts, introduce a new family of valid inequalities, and devise a new exact separation algorithm for all these cuts. We also establish a connection between these cuts and the edge-polytope of a bipartite graph, which gives new insight into the strength of known classes of inequalities as well. Finally, we evaluate the various classes of cuts on benchmark instances from the literature.
      原文链接:
    • NSTL
    • Elsevier

    List star edge-coloring of claw-free subcubic multigraphs

    Cui Q.Han Z.
    7页
    查看更多>>摘要：? 2021 Elsevier B.V.A star edge-coloring of a multigraph G is a proper edge-coloring of G such that no path or cycle of length four is bi-colored. The star chromatic index of G is the minimum number of colors needed to guarantee that G admits a star edge-coloring. The list star chromatic index of G is the smallest integer 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, Mohar and ?ámal proved that every subcubic multigraph has star chromatic index at most 7, and conjectured that 7 can be further improved to 6. Lu?ar, Mockov?iaková and Soták strengthened the result of Dvo?ák, Mohar and ?ámal by showing that every subcubic multigraph has list star chromatic index at most 7. In this paper, we verify the conjecture of Dvo?ák, Mohar and ?ámal for a class of subcubic multigraphs. We prove that every claw-free subcubic multigraph has list star chromatic index at most 6, and give a few examples to show that the upper bound is tight.
      原文链接:
    • NSTL
    • Elsevier

    The smallest pair of cospectral cubic graphs with different chromatic indexes

    Yan Z.Wang W.
    4页
    查看更多>>摘要：? 2021 Elsevier B.V.Using an exhaustive search on cubic graphs of order 16, we find a unique cospectral pair with different chromatic indexes. This example indicates that the chromatic index of a regular graph is not characterized by its spectrum, which answers a question recently posed in Etesami and Haemers (2020). We prove that any orthogonal matrix representing the similarity between the two adjacency matrices of the cospectral pair cannot be rational. This implies that the cospectral pair cannot be obtained using the original GM-switching method or its generalizations based on rational orthogonal matrices.
      原文链接:
    • NSTL
    • Elsevier