| 1. |
- Asratian, Armen, 1951-, et al.
(författare)
-
Two sensitivity theorems in fuzzy integer programming
- 2004
-
Ingår i: Discrete Applied Mathematics. - 0166-218X .- 1872-6771. ; 134:1-3, s. 129-140
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of estimating optima of covering integer linear programs with 0-1 variables under the following conditions: we do not know exact values of elements in the constraint matrix A but we know what elements of A are zero and what are nonzero, and also know minimal and maximal values of nonzero elements. We find bounds for variation of the optima of such programs in the worst and average cases. We also find some conditions guaranteeing that the variation of the optimum of such programs in the average case is close to 1 as the number of variables tends to infinity. This means that the values of nonzero elements in A can vary without significantly affecting the value of the optimum of the integer program.
|
|
| 2. |
- Bandelt, HJ, et al.
(författare)
-
Quasi-median graphs from sets of partitions
- 2002
-
Ingår i: Discrete Applied Mathematics. - 0166-218X .- 1872-6771. ; 122:23-35, s. 23-35
-
Tidskriftsartikel (populärvet., debatt m.m.)abstract
- In studies of molecular evolution, one is typically confronted with the task of inferring a phylogenetic tree from a set X of sequences of length n over a finite alphabet Lambda. For studies that invoke parsimony, it has been found helpful to consider the quasi-median graph generated by X in the Hamming graph Lambda(n). Although a great deal is already known about quasi-median graphs (and their algebraic counterparts), little is known about the quasi-median generation in Lambda(n) starting from a set X of vertices. We describe the vertices of the quasi-median graph generated by X in terms of the coordinatewise partitions of X. In particular, we clarify when the generated quasi-median graph is the so-called relation graph associated with X. This immediately characterizes the instances where either a block graph or the total Hamming graph is generated.
|
|
| 3. |
- Borgefors, G., et al.
(författare)
-
Editorial
- 2003
-
Ingår i: Discrete Applied Mathematics. - 0166-218X .- 1872-6771. ; 125:1, s. 1-2
-
Tidskriftsartikel (refereegranskat)
|
|
| 4. |
- Danev, Danyo
(författare)
-
Some constructions of superimposed codes in Euclidean spaces
- 2003
-
Ingår i: Discrete Applied Mathematics. - 0166-218X .- 1872-6771. ; 128:1 SPEC., s. 85-101
-
Tidskriftsartikel (refereegranskat)abstract
- We describe three new methods for obtaining superimposed codes in Euclidean spaces. With help of them we construct codes with parameters improving upon known constructions. We also prove that the spherical simplex code is not optimal as superimposed code at least for dimensions greater than 9. © 2003 Elsevier Science B.V. All rights reserved.
|
|
| 5. |
- Andren, Daniel, et al.
(författare)
-
The bivariate ising polynomial of a graph
- 2009
-
Ingår i: Discrete Applied Mathematics. - : Elsevier. - 0166-218X .- 1872-6771. ; 157:11, s. 2515-2524
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we discuss the two variable Ising polynomials in a graph theoretical setting. This polynomial has its origin in physics as the partition function of the Ising model with an external field. We prove some basic properties of the Ising polynomial and demonstrate that it encodes a large amount of combinatorial information about a graph. We also give examples which prove that certain properties, such as the chromatic number, are not determined by the Ising polynomial. Finally we prove that there exist large families of non-isomorphic planar triangulations with identical Ising polynomial. (C) 2009 Published by Elsevier B.V.
|
|
| 6. |
- Asratian, Armen, et al.
(författare)
-
Cyclic deficiency of graphs
- 2019
-
Ingår i: Discrete Applied Mathematics. - : ELSEVIER. - 0166-218X .- 1872-6771. ; 266, s. 171-185
-
Tidskriftsartikel (refereegranskat)abstract
- A proper edge coloring of a graph G with colors 1, 2, . . . , t is called a cyclic interval t-coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. In this paper we introduce and investigate a new notion, the cyclic deficiency of a graph G, defined as the minimum number of pendant edges whose attachment to G yields a graph admitting a cyclic interval coloring; this number can be considered as a measure of closeness of G of being cyclically interval colorable. We determine or bound the cyclic deficiency of several families of graphs. In particular, we present examples of graphs of bounded maximum degree with arbitrarily large cyclic deficiency, and graphs whose cyclic deficiency approaches the number of vertices. Finally, we conjecture that the cyclic deficiency of any graph does not exceed the number of vertices, and we present several results supporting this conjecture. (C) 2018 Elsevier B.V. All rights reserved.
|
|
| 7. |
- Asratian, Armen, Professor, 1951-, et al.
(författare)
-
Decomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules
- 2023
-
Ingår i: Discrete Applied Mathematics. - : ELSEVIER. - 0166-218X .- 1872-6771. ; 335, s. 25-35
-
Tidskriftsartikel (refereegranskat)abstract
- A graph G is called interval colorable if it has a proper edge coloring with colors 1, 2, 3, ... such that the colors of the edges incident to every vertex of G form an interval of integers. Not all graphs are interval colorable; in fact, quite few families have been proved to admit interval colorings. In this paper we introduce and investigate a new notion, the interval coloring thickness of a graph G, denoted theta int(G), which is the minimum number of interval colorable edge-disjoint subgraphs of G whose union is G. Our investigation is motivated by scheduling problems with compactness require-ments, in particular, problems whose solution may consist of several schedules, but where each schedule must not contain any waiting periods or idle times for all involved parties. We first prove that every connected properly 3-edge colorable graph with maximum degree 3 is interval colorable, and using this result, we deduce an upper bound on theta int(G) for general graphs G. We demonstrate that this upper bound can be improved in the case when G is bipartite, planar or complete multipartite and consider some applications in timetabling.
|
|
| 8. |
- Asratian, Armen, et al.
(författare)
-
On Hamiltonicity of regular graphs with bounded second neighborhoods
- 2022
-
Ingår i: Discrete Applied Mathematics. - : Elsevier. - 0166-218X .- 1872-6771. ; 316, s. 75-86
-
Tidskriftsartikel (refereegranskat)abstract
- Let G(k) denote the set of connected k-regular graphs G, k ≥ 2, where the number of vertices at distance 2 from any vertex in G does not exceed k. Asratian (2006) showed (using other terminology) that a graph G ∈ G(k) is Hamiltonian if for each vertex u of G the subgraph induced by the set of vertices at distance at most 2 from u is 2-connected. We prove here that in fact all graphs in the sets G(3), G(4) and G(5) are Hamiltonian. We also prove that the problem of determining whether there exists a Hamilton cycle in a graph from G(6) is NP-complete. Nevertheless we show that every locally connected graph G ∈ G(k), k ≥ 6, is Hamiltonian and that for each non-Hamiltonian cycle C in G there exists a cycle C' of length |V(C)|+l in G, l ∈ {1, 2}, such that V(C) ⊂ V(C). Finally, we note that all our conditions for Hamiltonicity apply to infinitely many graphs with large diameters.
|
|
| 9. |
- Asratian, Armen, 1951-, et al.
(författare)
-
Some local–global phenomena in locally finite graphs
- 2021
-
Ingår i: Discrete Applied Mathematics. - : Elsevier. - 0166-218X .- 1872-6771. ; 293, s. 166-176
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we present some results for a connected infinite graph G with finite degrees where the properties of balls of small radii guarantee the existence of some Hamiltonian and connectivity properties of G. (For a vertex w of a graph G the ball of radius r centered at w is the subgraph of G induced by the set Mr(w) of vertices whose distance from w does not exceed r). In particular, we prove that if every ball of radius 2 in G is 2-connected and G satisfies the condition dG(u)+dG(v)≥|M2(w)|−1 for each path uwv in G, where u and v are non-adjacent vertices, then G has a Hamiltonian curve, introduced by Kündgen et al. (2017). Furthermore, we prove that if every ball of radius 1 in G satisfies Ore’s condition (1960) then all balls of any radius in G are Hamiltonian.
|
|
| 10. |
- Bang-Jensen, Jorgen, et al.
(författare)
-
Restricted cycle factors and arc-decompositions of digraphs
- 2015
-
Ingår i: Discrete Applied Mathematics. - : Elsevier. - 0166-218X .- 1872-6771. ; 193, s. 80-93
-
Tidskriftsartikel (refereegranskat)abstract
- We study the complexity of finding 2-factors with various restrictions as well as edge-decompositions in (the underlying graphs of) digraphs. In particular we show that it is N P-complete to decide whether the underlying undirected graph of a digraph D has a 2-factor with cycles C-1, C-2, ..., C-k such that at least one of the cycles C-i is a directed cycle in D (while the others may violate the orientation back in D). This solves an open problem from J. Bang-Jensen et al., Vertex-disjoint directed and undirected cycles in general digraphs, JCT B 106 (2014), 1-14. Our other main result is that it is also N P-complete to decide whether a 2-edge-colored bipartite graph has two edge-disjoint perfect matchings such that one of these is monochromatic (while the other does not have to be). We also study the complexity of a number of related problems. In particular we prove that for every even k greater than= 2, the problem of deciding whether a bipartite digraph of girth k has a k-cycle-free cycle factor is N P-complete. Some of our reductions are based on connections to Latin squares and so-called avoidable arrays.
|
|
