Year 2021

• Independent Domination Subdivision in Graphs

  Publication

  • A. Babikir
  • M. Dettlaff
  • M. A. Henning
  • M. Lemańska

  - GRAPHS AND COMBINATORICS - Year 2021

  A set $S$ of vertices in a graph $G$ is a dominating set if every vertex not in $S$ is adjacent to a vertex in~$S$. If, in addition, $S$ is an independent set, then $S$ is an independent dominating set. The independent domination number $i(G)$ of $G$ is the minimum cardinality of an independent dominating set in $G$. The independent domination subdivision number $\sdi(G)$ is the minimum number of edges that must be subdivided (each...

  Full text available to download

Year 2018

• Dynamic F-free Coloring of Graphs

  Publication

  • P. Borowiecki
  • E. Sidorowicz

  - GRAPHS AND COMBINATORICS - Year 2018

  A problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well...

  Full text available to download

• Total Domination Versus Domination in Cubic Graphs

  Publication

  • J. Cyman
  • M. Dettlaff
  • M. A. Henning
  • M. Lemańska
  • J. Raczek

  - GRAPHS AND COMBINATORICS - Year 2018

  A dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number,γ(G), and total domination number, γ_t(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, \Gamma(G), and the upper total domination...

  Full text available to download

Year 2015

• The Backbone Coloring Problem for Bipartite Backbones

  Publication

  • R. Janczewski
  • K. Turowski

  - GRAPHS AND COMBINATORICS - Year 2015

  Let G be a simple graph, H be its spanning subgraph and λ≥2 be an integer. By a λ -backbone coloring of G with backbone H we mean any function c that assigns positive integers to vertices of G in such a way that |c(u)−c(v)|≥1 for each edge uv∈E(G) and |c(u)−c(v)|≥λ for each edge uv∈E(H) . The λ -backbone chromatic number BBCλ(G,H) is the smallest integer k such that there exists a λ -backbone coloring c of G with backbone H satisfying...

  Full text to download in external service

Year 2014

• Counting Lattice Paths With Four Types of Steps

  Publication

  • M. Dziemiańczuk

  - GRAPHS AND COMBINATORICS - Year 2014

• Some Progress on Total Bondage in Graphs

  Publication

  • N. J. Rad
  • J. Raczek

  - GRAPHS AND COMBINATORICS - Year 2014

  The total bondage number b_t(G) of a graph G with no isolated vertex is the cardinality of a smallest set of edges E'⊆E(G) for which (1) G−E' has no isolated vertex, and (2) γ_t(G−E')>γ_t(G). We improve some results on the total bondage number of a graph and give a constructive characterization of a certain class of trees achieving the upper bound on the total bondage number.

  Full text available to download

Year 2008

• Tighter bounds on the size of a maximum P3-matching in a cubic graph

  Publication

  • A. Kosowski
  • M. Małafiejski
  • P. Żyliński

  - GRAPHS AND COMBINATORICS - Year 2008

  W pracy pokazano, że największe P3-skojarzenie dla dowolnego grafu o n>16 wierzchołkach składa się z przynajmniej 117n/152 wierzchołków.

  Full text to download in external service