# DISCRETE APPLIED MATHEMATICS - Journal - MOST Wiedzy

## DISCRETE APPLIED MATHEMATICS

0166-218X

1872-6771

### Disciplines (Field of Science):

• Automation, electronic and electrical engineering (Engineering and Technology)
• Information and communication technology (Engineering and Technology)
• Mechanical engineering (Engineering and Technology)
• Management and quality studies (Social studies)
• Computer and information sciences (Natural sciences)
• Mathematics (Natural sciences)

### Ministry points: Help

Ministry points - current year
Year Points List
Year 2021 70 Ministry Scored Journals List 2019
Ministry points - previous years
Year Points List
2021 70 Ministry Scored Journals List 2019
2020 70 Ministry Scored Journals List 2019
2019 70 Ministry Scored Journals List 2019
2018 25 A
2017 25 A
2016 25 A
2015 25 A
2014 25 A
2013 25 A
2012 25 A
2011 25 A
2010 20 A
2009 20 A
2008 20 A

Hybrid

### Points CiteScore:

Points CiteScore - current year
Year Points
Year 2019 2
Points CiteScore - previous years
Year Points
2019 2
2018 1.9
2017 1.9
2016 1.9
2015 1.8
2014 1.5
2013 1.6
2012 2
2011 1.9

### Papers published in journal

• results on page:
• year:
title:
citation:

total: 33

#### Catalog Journals

##### Year 2019
• ###### Equitable coloring of hypergraphs
Publication

- Year 2019

A hypergraph is equitablyk-colorable if its vertices can be partitioned into k sets/colorclasses in such a way that monochromatic edges are avoided and the number of verticesin any two color classes differs by at most one. We prove that the problem of equitable 2-coloring of hypergraphs is NP-complete even for 3-uniform hyperstars. Finally, we apply the method of dynamic programming for designing a polynomial-time algorithm to...

• ###### Global edge alliances in graphs
Publication

- Year 2019

In the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...

• ###### On the super domination number of lexicographic product graphs
Publication

- Year 2019

The neighbourhood of a vertexvof a graphGis the setN(v) of all verticesadjacent tovinG. ForD⊆V(G) we defineD=V(G)\D. A setD⊆V(G) is called a super dominating set if for every vertexu∈D, there existsv∈Dsuch thatN(v)∩D={u}. The super domination number ofGis theminimum cardinality among all super dominating sets inG. In this article weobtain closed formulas and tight bounds for the super dominating number oflexicographic product...

• ###### Weakly connected Roman domination in graphs
Publication

- Year 2019

A Roman dominating function on a graph G=(V,E) is defined to be a function f :V → {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v)=2. A dominating set D⊆V is a weakly connected dominating set of G if the graph (V,E∩(D×V)) is connected. We define a weakly connected Roman dominating function on a graph G to be a Roman dominating function such that the set...

##### Year 2018
• ###### Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
Publication

- Year 2018

We consider the problem of scheduling n identical jobs on 3 uniform machines with speeds s1, s2, and s3 to minimize the schedule length. We assume that jobs are subject to some kind of mutual exclusion constraints, modeled by a cubic incompatibility graph. We how that if the graph is 2-chromatic then the problem can be solved in O(n^2) time. If the graph is 3-chromatic, the problem becomes NP-hard even if s1&gt;s2=s3.

• ###### Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
Publication

- Year 2018

We consider the complexity of semi-equitable k-coloring, k&gt;3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s&gt;n/3, and it is polynomially solvable if s, n/3.

##### Year 2016
• ###### Edge-coloring of 3-uniform hypergraphs
Publication

- Year 2016

We consider edge-colorings of 3-uniform hypergraphs which is a natural generalization of the problem of edge-colorings of graphs. Various classes of hypergraphs are discussed and we make some initial steps to establish the border between polynomial and NP-complete cases. Unfortunately, the problem appears to be computationally difficult even for relatively simple classes of hypergraphs.

• ###### On bipartization of cubic graphs by removal of an independent set
Publication

- Year 2016

We study a new problem for cubic graphs: bipartization of a cubic graph Q by deleting sufficiently large independent set.

##### Year 2015
• ###### Interval incidence graph coloring
Publication

- Year 2015

In this paper we introduce a concept of interval incidence coloring of graphs and survey its general properties including lower and upper bounds on the number of colors. Our main focus is to determine the exact value of the interval incidence coloring number χii for selected classes of graphs, i.e. paths, cycles, stars, wheels, fans, necklaces, complete graphs and complete k-partite graphs. We also study the complexity of the...

• ###### New potential functions for greedy independence and coloring
Publication

- Year 2015

A potential function $f_G$ of a finite, simple and undirected graph $G=(V,E)$ is an arbitrary function $f_G : V(G) \rightarrow \mathbb{N}_0$ that assigns a nonnegative integer to every vertex of a graph $G$. In this paper we define the iterative process of computing the step potential function $q_G$ such that $q_G(v)\leq d_G(v)$ for all $v\in V(G)$. We use this function in the development of new Caro-Wei-type and Brooks-type...

• ###### The computational complexity of the backbone coloring problem for planar graphs with connected backbones
Publication

- Year 2015

In the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...

##### Year 2014
• ###### Bondage number of grid graphs
Publication

- Year 2014

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number of G. Here we study the bondage number of some grid-like graphs. In this sense, we obtain some bounds or exact values of the bondage number of some strong product and direct product of two paths.

• ###### Interval incidence coloring of bipartite graphs
Publication

- Year 2014

In this paper we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (χii) for bipartite graphs χii≤2Δ, and we prove that χii=2Δ holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic...

• ###### On the partition dimension of trees
Publication

- Year 2014

Given an ordered partition Π={P1,P2,…,Pt} of the vertex set V of a connected graph G=(V,E), the partition representation of a vertex v∈V with respect to the partition Π is the vector r(v|Π)=(d(v,P1),d(v,P2),…,d(v,Pt)), where d(v,Pi) represents the distance between the vertex vv and the set Pi. A partition Π of V is a resolving partition of G if different vertices of G have different partition representations, i.e., for every...

##### Year 2013
• ###### Three-fast-searchable graphs
Publication

- Year 2013

In the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates...

##### Year 2012
• ###### On the size of identifying codes in triangle-free graphs
Publication

- Year 2012

In an undirected graph G, a subset C⊆V(G) such that C is a dominating set of G, and each vertex in V(G) is dominated by a distinct subset of vertices from C, is called an identifying code of G. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph G, let gammaID(G) be the minimum cardinality of an identifying code in G. In this paper, we show that for any connected...

##### Year 2011
• ###### A note on total reinforcement in graphs
Publication

- Year 2011

In this note we prove a conjecture and inprove some results presendet in a recent paper of N. Sridharan, M.D. Elias, V.S.A. Subramanian, Total reinforcement number of a graph, AKCE Int. J. Graphs Comb. 4 (2) (2007) 197-202.

##### Year 2010
• ###### A note on the weakly convex and convex domination numbers of a torus
Publication

- Year 2010

W pracy określone są liczby liczby dominowania i dominowania wypukłego torusów, czyli iloczynów kartezjańskich dwóch cykli.

##### Year 2009
• ###### A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints
Publication

- Year 2009

We address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem...

• ###### A note on the strength and minimum color sum of bipartite graphs
Publication

- Year 2009

Siłą grafu G nazywamy najmniejszą liczbę całkowitą s, taką że istniej pokolorowanie grafu G, o minimalnej sumie przy użyciu kolorów {1,...,s}. W pracy pokazano, że w grafach dwudzielnych stopnia D zachodzi oszacowanie s &lt;= ceil(D/2) + 1. Z obserwacji tej wynika algorytm wielomianowy do obliczania siły i sumy chromatycznej w grafach dwudzielnych stopnia co najwyżej 4.

• ###### Approximating the maximum 2- and 3-edge-colorable subgraph problems
Publication

- Year 2009

Dla ustalonej wartości parametru k&gt;=2, problem maksymalnego podgrafu krawędziowo k-kolorowalnego polega na wskazaniu k rozłącznych skojarzeń w grafie prostym, a kryterium optymalizacji jest maksymalizacja całkowitej liczby użytych krawędzi. W pracy podano algorytmy 5/6- i 4/5-przybliżone odpowiednio dla przypadków k=2 i k=3, poprawiając wyniki znane z literatury.

• ###### Forwarding and optical indices of a graph
Publication

- Year 2009

W pracy rozstrzygnięto dwa problemy dotyczące komunikacji wszyscy-do-wszystkich w grafach. Stwierdzono, że dla wersji skierowanej problemu parametry ''pi'' (maksymalne obciążenie krawędzi) i ''w'' (parametr chromatyczny) nie muszą być w ogólności sobie równe. Dla wersji nieskierowanej problemu pokazano, że wyznaczenie wartości zarówno ''pi'', jak i ''w'', jest w ogólności problemem NP-trudnym.

• ###### Total outer-connected domination numbers of trees
Publication

- Year 2009

Niech G=(V,E) będzie grafem bez wierzchołków izolowanych. Zbiór wierzchołków D nazywamy zbiorem dominującym totalnym zewnętrznie spójnym jeżli każdy wierzchołek grafu ma sąsiada w D oraz podgraf indukowany przez V-D jest grafem spójnym. Moc najmniejszego zbioru D o takich własnościach nazywamy liczbą dominowania totalnego zewnątrznie spójnego. Praca m.in. zawiera dolne ograniczenie na liczbę dominowania totalnego zewnętrznie spójnego...

##### Year 2008
• ###### Edge ranking and searching in partial orders
Publication

- Year 2008

Artykuł jest poświęcony problemowi konstrukcji optymalnej (wymagającej minimalnej ilości porównań/zapytań) strategii wyszukiwania elementu w częściowym porządku. W pracy wskazano związki pomiędzy tym problemem oraz uporządkowanym kolorowaniem krawędzi grafów, co implikuje liniowy algorytm dla częściowych porządków o strukturze drzewa. Pokazano również, że znalezienie optymalnej strategii jest problemem obliczeniowo trudnym dla...

##### Year 2007
• ###### Easy and hard instances of arc ranking in directed graphs
Publication

- Year 2007

Artykuł dotyczy uporządkowanego kolorowania łuków grafów skierowanych. Problem polega na takim przyporządkowaniu liczb łukom digrafu, aby każda skierowana ścieżka łącząca dwa łuki o tej samej liczbie (kolorze) zawierała łuk o kolorze wyższym. Praca podaje liniowy optymalny algorytm dla pewnego szczególnego przypadku, oraz zawiera dowód, iż problem ten jest obliczeniowo trudny dla 3-dzielnych acyklicznych digrafów i stałej liczby...

Publication

- Year 2004

##### Year 2003
• ###### A polynomial algorithm for finding T-span of generalized cacti
Publication
• K. Giaro
• R. Janczewski
• M. Małafiejski

- Year 2003

• ###### A polynomial algorithm for finding T-span of generalized cacti.
Publication

- Year 2003

W pracy opisano wielomianowy algorytm wyznaczający optymalne T-pokolorowania dla uogólnionych kaktusów.

• ###### The complexity of the T-coloring problem for graphs with small degree
Publication
• K. Giaro
• R. Janczewski
• M. Małafiejski

- Year 2003

• ###### The complexity of the T-coloring problem for graphs with small degree.
Publication

- Year 2003

W pracy ustalono złożoność obliczeniową problemu optymalnego kolorowania grafów o ustalonym stopniu.

Publication

- Year 1999

Publication

- Year 1997