## Currently displaying 1 – 8 of 8

Showing per page

Order by Relevance | Title | Year of publication

### Nowhere-zero $k$-flows of supergraphs.

The Electronic Journal of Combinatorics [electronic only]

### The Grötzsch theorem for the hypergraph of maximal cliques.

The Electronic Journal of Combinatorics [electronic only]

### Gallai's innequality for critical graphs of reducible hereditary properties

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, $=₁\circ ₂\circ ...\circ ₖ$ and $\delta ={\sum }_{i=1}^{k}\delta {\left(}_{i}\right)$. 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}_{\delta +1}$. The generalization of Gallai’s inequality for -choice critical graphs is also presented.

### Parity vertex colorings of binomial trees

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  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

Mathematica Bohemica

Let $\alpha \left(n\right)$ be the least number $k$ for which there exists a simple graph with $k$ vertices having precisely $n\ge 3$ spanning trees. Similarly, define $\beta \left(n\right)$ as the least number $k$ for which there exists a simple graph with $k$ edges having precisely $n\ge 3$ spanning trees. As an $n$-cycle has exactly $n$ spanning trees, it follows that $\alpha \left(n\right),\beta \left(n\right)\le n$. In this paper, we show that $\alpha \left(n\right)\le \frac{1}{3}\left(n+4\right)$ and $\beta \left(n\right)\le \frac{1}{3}\left(n+7\right)$ if and only if $n\notin \left\{3,4,5,6,7,9,10,13,18,22\right\}$, which is a subset of Euler’s idoneal numbers. Moreover, if $n¬\equiv 2\phantom{\rule{4.44443pt}{0ex}}\left(mod\phantom{\rule{0.277778em}{0ex}}3\right)$ and $n\ne 25$ we show that $\alpha \left(n\right)\le \frac{1}{4}\left(n+9\right)$ and $\beta \left(n\right)\le \frac{1}{4}\left(n+13\right).$ This improves some previously estabilished bounds.

### Hajós' theorem for list colorings of hypergraphs

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

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