Page 1 Next

## Displaying 1 – 20 of 657

Showing per page

### 1 -Faktoren von Graphen.

Mathematische Annalen

### 2-factors in claw-free graphs with locally disconnected vertices

Czechoslovak Mathematical Journal

An edge of $G$ is singular if it does not lie on any triangle of $G$; otherwise, it is non-singular. A vertex $u$ of a graph $G$ is called locally connected if the induced subgraph $G\left[N\left(u\right)\right]$ by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph $G$ of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex $v$ of degree at least $3$ in $G,$ there is a nonnegative integer $s$ such that $v$ lies...

### 2-placement of (p,q)-trees

Discussiones Mathematicae Graph Theory

Let G = (L,R;E) be a bipartite graph such that V(G) = L∪R, |L| = p and |R| = q. G is called (p,q)-tree if G is connected and |E(G)| = p+q-1. Let G = (L,R;E) and H = (L',R';E') be two (p,q)-tree. A bijection f:L ∪ R → L' ∪ R' is said to be a biplacement of G and H if f(L) = L' and f(x)f(y) ∉ E' for every edge xy of G. A biplacement of G and its copy is called 2-placement of G. A bipartite graph G is 2-placeable if G has a 2-placement. In this paper we give all (p,q)-trees which...

### 4-critical 4-valent planar graphs constructed with crowns.

Mathematica Scandinavica

### A bisection method for the traveling salesman problem

Applicationes Mathematicae

### A bound on the $k$-domination number of a graph

Czechoslovak Mathematical Journal

Let $G$ be a graph with vertex set $V\left(G\right)$, and let $k\ge 1$ be an integer. A subset $D\subseteq V\left(G\right)$ is called a $k$-dominating set if every vertex $v\in V\left(G\right)-D$ has at least $k$ neighbors in $D$. The $k$-domination number ${\gamma }_{k}\left(G\right)$ of $G$ is the minimum cardinality of a $k$-dominating set in $G$. If $G$ is a graph with minimum degree $\delta \left(G\right)\ge k+1$, then we prove that ${\gamma }_{k+1}\left(G\right)\le \frac{|V\left(G\right)|+{\gamma }_{k}\left(G\right)}{2}.$ In addition, we present a characterization of a special class of graphs attaining equality in this inequality.

### A characterization of diameter-2-critical graphs with no antihole of length four

Open Mathematics

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence...

### A characterization of graphs in which some minimum dominating set covers all the edges

Czechoslovak Mathematical Journal

### A characterization of the decay number of a connected graph

Mathematica Slovaca

### A combinatorial ranking problem.

Aequationes mathematicae

### A combinatorial ranking problem. (Short Communication).

Aequationes mathematicae

### A conjecture on cycle-pancyclism in tournaments

Discussiones Mathematicae Graph Theory

Let T be a hamiltonian tournament with n vertices and γ a hamiltonian cycle of T. In previous works we introduced and studied the concept of cycle-pancyclism to capture the following question: What is the maximum intersection with γ of a cycle of length k? More precisely, for a cycle Cₖ of length k in T we denote ${I}_{\gamma }\left(Cₖ\right)=|A\left(\gamma \right)\cap A\left(Cₖ\right)|$, the number of arcs that γ and Cₖ have in common. Let $f\left(k,T,\gamma \right)=max{I}_{\gamma }\left(Cₖ\right)|Cₖ\subset T$ and f(n,k) = minf(k,T,γ)|T is a hamiltonian tournament with n vertices, and γ a hamiltonian cycle of T. In previous papers we gave...

### A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles

Kybernetika

For any $d\ge 11$ we construct graphs of degree $d$, diameter $2$, and order $\frac{8}{25}{d}^{2}+O\left(d\right)$, obtained as lifts of dipoles with voltages in cyclic groups. For Cayley Abelian graphs of diameter two a slightly better result of $\frac{9}{25}{d}^{2}+O\left(d\right)$ has been known  but it applies only to special values of degrees $d$ depending on prime powers.

### A Décomposition Theorem on Euclidean Steiner Minimal Trees.

Discrete &amp; computational geometry

### A Different Short Proof of Brooks’ Theorem

Discussiones Mathematicae Graph Theory

Lovász gave a short proof of Brooks’ theorem by coloring greedily in a good order. We give a different short proof by reducing to the cubic case.

### A generalization of a theorem of Turán for valuated graphs

Časopis pro pěstování matematiky

### A generalization of Hamiltonian cycles for trees

Czechoslovak Mathematical Journal

### A graph and its complement with specified properties. III: Girth and circumference.

International Journal of Mathematics and Mathematical Sciences

### A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs.

Journal of Graph Algorithms and Applications

### A linear pseudo-Boolean viewpoint on matching and other central concepts in graph theory

Applicationes Mathematicae

Page 1 Next