Year 2016

• Weakly convex and convex domination numbers of some products of graphs

  Publication

  • A. Kucieńska
  • M. Lemańska
  • J. Raczek

  - ARS COMBINATORIA - Year 2016

  If $G=(V,E)$ is a simple connected graph and $a,b\in V$, then a shortest $(a-b)$ path is called a $(u-v)$-{\it geodesic}. A set $X\subseteq V$ is called {\it weakly convex} in $G$ if for every two vertices $a,b\in X$ exists $(a-b)$- geodesic whose all vertices belong to $X$. A set $X$ is {\it convex} in $G$ if for every $a,b\in X$ all vertices from every $(a-b)$-geodesic belong to $X$. The {\it weakly convex domination number}...

Year 2015

• On some Zarankiewicz numbers and bipartite Ramsey Numbers for Quadrilateral

  Publication

  • J. Dybizbański
  • T. Dzido
  • S. Radziszowski

  - ARS COMBINATORIA - Year 2015

  The Zarankiewicz number z ( m, n ; s, t ) is the maximum number of edges in a subgraph of K m,n that does not contain K s,t as a subgraph. The bipartite Ramsey number b ( n 1 , · · · , n k ) is the least positive integer b such that any coloring of the edges of K b,b with k colors will result in a monochromatic copy of K n i ,n i in the i -th color, for some i , 1 ≤ i ≤ k . If n i = m for all i , then we denote this number by b k ( m )....

  Full text available to download

• Unicyclic graphs with equal total and total outer-connected domination numbers

  Publication

  • J. Raczek

  - ARS COMBINATORIA - Year 2015

  Let G = (V,E) be a graph without an isolated vertex. A set D ⊆ V (G) is a total dominating set if D is dominating and the in- duced subgraph G[D] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total domi- nating set of G. A set D ⊆ V (G) is a total outer–connected dominating set if D is total dominating and the induced subgraph G[V (G)−D] is a connected graph. The total outer–connected...

  Full text to download in external service

Year 2011

• On trees with double domination number equal to total domination number plus one

  Publication

  • M. Krzywkowski

  - ARS COMBINATORIA - Year 2011

  A total dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D. A vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The total (double, respectively) domination number of a graph G is the minimum cardinality of a total (double,...

  Full text available to download

• The hat problem on cycles on at least nine vertices

  Publication

  • M. Krzywkowski

  - ARS COMBINATORIA - Year 2011

  The topic is the hat problem in which each of n players is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of winning. In this version every player...

  Full text available to download

Year 2008

• Packing Three-Vertex Paths in 2-Connected Cubic Graphs

  Publication

  • A. Kosowski
  • P. Żyliński

  - ARS COMBINATORIA - Year 2008

  W pracy rozważano problem rozmieszczanie ścieżek P3 w 2-spójnych grafach 3-regularnych. Pokazano, że w 2-spójnym grafie 3-regularnym o n wierzchołkach można zawsze pokryć 9/11 n wierzchołków przez ścieżki P3; podano także odpowiednie oszacowania górne.

  Full text to download in external service

• The complexity of list ranking of trees

  Publication

  • D. Dereniowski

  - ARS COMBINATORIA - Year 2008

  Uporządkowane kolorowanie grafu polega na takim etykietowaniu jego wierzchołków, aby każda ścieżka łącząca dwa wierzchołki o tym samym kolorze zawierała wierzchołek o kolorze wyższym. Jeśli każdy wierzchołek posiada dodatkowo listę dozwolonych dla niego etykiet, to mówimy wówczas o uporządkowanym listowym kolorowaniu wierzchołków. W pracy wskazano szereg klas grafów, dla których problem jest trudny: pełne drzewa binarne, drzewa...

  Full text to download in external service