Anna Fiedorowicz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Anna Fiedorowicz has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Elżbieta Sidorowicz
University of Zielona Góra
5 shared publications - Mariusz Hałuszczak
Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Z. Szafrana 4a, 65-516 Zielona Góra, Poland
1 shared publication - Mieczysław Borowiecki
University of Zielona Góra
1 shared publication - Mieczysław Borowiecki
Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Z.Szafrana 4a, Zielona Góra, Poland
1 shared publication - Zsolt Tuza
HUN‐REN Alfréd Rényi Institute of Mathematics Budapest Hungary
1 shared publication
Latest Publications
- 1 September 2020
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 284, 99-110
Independent -domination in -trees- 1 September 2020
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 284, 99-110
Independent -domination in -trees- Open Access
- 1 January 2019
- Published by National Library of Serbia in Applicable Analysis and Discrete Mathematics
- Vol. 13 (1) , 261-289
Connected domination game
In this paper we introduce a domination game based on the notion of connected domination. Let G = (V,E) be a connected graph of order at least 2. We define a connected domination game on G as follows: The game is played by two players, Dominator and Staller. The players alternate taking turns choosing a vertex of G (Dominator starts). A move of a player by choosing a vertex v is legal, if (1) the vertex v dominates at least one additional vertex that was not dominated by the set of previously chosen vertices and (2) the set of all chosen vertices induces a connected subgraph of G. The game ends when none of the players has a legal move (i.e., G is dominated). The aim of Dominator is to finish as soon as possible, Staller has an opposite aim. Let D be the set of played vertices obtained at the end of the connected domination game (D is a connected dominating set of G). The connected game domination number of G, denoted cg(G), is the minimum cardinality of D, when both players played optimally on G. We provide an upper bound on cg(G) in terms of the connected domination number. We also give a tight upper bound on this parameter for the class of 2-trees. Next, we investigate the Cartesian product of a complete graph and a tree, and we give exact values of the connected game domination number for such a product, when the tree is a path or a star. We also consider some variants of the game, in particular, a Staller-start game.
- 1 January 2019
- Published by National Library of Serbia in Applicable Analysis and Discrete Mathematics
- Vol. 13 (1) , 261-289
Open AccessConnected domination game
In this paper we introduce a domination game based on the notion of connected domination. Let G = (V,E) be a connected graph of order at least 2. We define a connected domination game on G as follows: The game is played by two players, Dominator and Staller. The players alternate taking turns choosing a vertex of G (Dominator starts). A move of a player by choosing a vertex v is legal, if (1) the vertex v dominates at least one additional vertex that was not dominated by the set of previously chosen vertices and (2) the set of all chosen vertices induces a connected subgraph of G. The game ends when none of the players has a legal move (i.e., G is dominated). The aim of Dominator is to finish as soon as possible, Staller has an opposite aim. Let D be the set of played vertices obtained at the end of the connected domination game (D is a connected dominating set of G). The connected game domination number of G, denoted cg(G), is the minimum cardinality of D, when both players played optimally on G. We provide an upper bound on cg(G) in terms of the connected domination number. We also give a tight upper bound on this parameter for the class of 2-trees. Next, we investigate the Cartesian product of a complete graph and a tree, and we give exact values of the connected game domination number for such a product, when the tree is a path or a star. We also consider some variants of the game, in particular, a Staller-start game.
- 21 January 2016
- Published by Springer Nature in Science China Mathematics
- Vol. 59 (7) , 1427-1440
Acyclic colorings of graphs with bounded degree
- 21 January 2016
- Published by Springer Nature in Science China Mathematics
- Vol. 59 (7) , 1427-1440
Acyclic colorings of graphs with bounded degree
- Open Access
Acyclic colourings of graphs with bounded degree
A $k$-colouring (not necessarily proper) of vertices of a graph is called {\it acyclic}, if for every pair of distinct colours $i$ and $j$ the subgraph induced by the edges whose endpoints have colours $i$ and $j$ is acyclic. In the paper we consider some generalised acyclic $k$-colourings, namely, we require that each colour class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic $5$-colouring such that each colour class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph $G$ has an acyclic 2-colouring in which each colour class induces a graph with maximum degree at most 3 is NP-complete, even for graphs with maximum degree 5. We also give a linear-time algorithm for an acyclic $t$-improper colouring of any graph with maximum degree $d$ assuming that the number of colors is large enough.Open AccessAcyclic colourings of graphs with bounded degree
A $k$-colouring (not necessarily proper) of vertices of a graph is called {\it acyclic}, if for every pair of distinct colours $i$ and $j$ the subgraph induced by the edges whose endpoints have colours $i$ and $j$ is acyclic. In the paper we consider some generalised acyclic $k$-colourings, namely, we require that each colour class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic $5$-colouring such that each colour class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph $G$ has an acyclic 2-colouring in which each colour class induces a graph with maximum degree at most 3 is NP-complete, even for graphs with maximum degree 5. We also give a linear-time algorithm for an acyclic $t$-improper colouring of any graph with maximum degree $d$ assuming that the number of colors is large enough. - 8 May 2014
- Published by Springer Nature in Science China Mathematics
- Vol. 57 (12) , 2485-2494
Acyclic improper colouring of graphs with maximum degree 4
- 8 May 2014
- Published by Springer Nature in Science China Mathematics
- Vol. 57 (12) , 2485-2494
Acyclic improper colouring of graphs with maximum degree 4
- 15 July 2012
- Published by Elsevier in Information Processing Letters
- Vol. 112 (13) , 557-561
Acyclic chromatic indices of fully subdivided graphs
- 15 July 2012
- Published by Elsevier in Information Processing Letters
- Vol. 112 (13) , 557-561
Acyclic chromatic indices of fully subdivided graphs
- 1 February 2011
- Published by Elsevier in Information Processing Letters
- Vol. 111 (6) , 287-290
Acyclic edge colourings of graphs with the number of edges linearly bounded by the number of vertices
- 1 February 2011
- Published by Elsevier in Information Processing Letters
- Vol. 111 (6) , 287-290
Acyclic edge colourings of graphs with the number of edges linearly bounded by the number of vertices