Currently displaying 1 – 8 of 8

Showing per page

Order by Relevance | Title | Year of publication

Gallai's innequality for critical graphs of reducible hereditary properties

Peter MihókRiste Skrekovski — 2001

Discussiones Mathematicae Graph Theory

In this paper Gallai’s inequality on the number of edges in critical graphs is generalized for reducible additive induced-hereditary properties of graphs in the following way. Let , , . . . , (k ≥ 2) be additive induced-hereditary properties, = . . . and δ = i = 1 k δ ( i ) . Suppose that G is an -critical graph with n vertices and m edges. Then 2m ≥ δn + (δ-2)/(δ²+2δ-2)*n + (2δ)/(δ²+2δ-2) unless = ² or G = K δ + 1 . The generalization of Gallai’s inequality for -choice critical graphs is also presented.

Parity vertex colorings of binomial trees

Petr GregorRiste Škrekovski — 2012

Discussiones Mathematicae Graph Theory

We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.

Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees

Jernej AzarijaRiste Škrekovski — 2013

Mathematica Bohemica

Let α ( n ) be the least number k for which there exists a simple graph with k vertices having precisely n 3 spanning trees. Similarly, define β ( n ) as the least number k for which there exists a simple graph with k edges having precisely n 3 spanning trees. As an n -cycle has exactly n spanning trees, it follows that α ( n ) , β ( n ) n . In this paper, we show that α ( n ) 1 3 ( n + 4 ) and β ( n ) 1 3 ( n + 7 ) if and only if n { 3 , 4 , 5 , 6 , 7 , 9 , 10 , 13 , 18 , 22 } , which is a subset of Euler’s idoneal numbers. Moreover, if n ¬ 2 ( mod 3 ) and n 25 we show that α ( n ) 1 4 ( n + 9 ) and β ( n ) 1 4 ( n + 13 ) . This improves some previously estabilished bounds.

Hajós' theorem for list colorings of hypergraphs

Claude BenzakenSylvain GravierRiste Skrekovski — 2003

Discussiones Mathematicae Graph Theory

A well-known theorem of Hajós claims that every graph with chromathic number greater than k can be constructed from disjoint copies of the complete graph K k + 1 by repeated application of three simple operations. This classical result has been extended in 1978 to colorings of hypergraphs by C. Benzaken and in 1996 to list-colorings of graphs by S. Gravier. In this note, we capture both variations to extend Hajós’ theorem to list-colorings of hypergraphs.

Modeling acquaintance networks based on balance theory

Vida VukašinovićJurij ŠilcRiste Škrekovski — 2014

International Journal of Applied Mathematics and Computer Science

An acquaintance network is a social structure made up of a set of actors and the ties between them. These ties change dynamically as a consequence of incessant interactions between the actors. In this paper we introduce a social network model called the Interaction-Based (IB) model that involves well-known sociological principles. The connections between the actors and the strength of the connections are influenced by the continuous positive and negative interactions between the actors and, vice...

Page 1

Download Results (CSV)