Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "Broersma, Hajo" wg kryterium: Autor

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-9 z 9
    Tytuł:
    Spanning trees with many or few colors in edge-colored graphs
    Autorzy:
    Broersma, Hajo
    Li, Xueliang
    Powiązania:
    https://bibliotekanauki.pl/articles/971955.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge-coloring
    spanning tree
    matroid (intersection)
    complexity
    NP-complete
    NP-hard
    polynomial algorithm
    (minimum) dominating set
    Opis:
    Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 2; 259-269
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Isomorphisms and traversability of directed path graphs
    Autorzy:
    Broersma, Hajo
    Li, Xueliang
    Powiązania:
    https://bibliotekanauki.pl/articles/743350.pdf
    Data publikacji:
    2002
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    directed path graph
    line digraph
    isomorphism
    travers-ability
    Opis:
    The concept of a line digraph is generalized to that of a directed path graph. The directed path graph Pₖ(D) of a digraph D is obtained by representing the directed paths on k vertices of D by vertices. Two vertices are joined by an arc whenever the corresponding directed paths in D form a directed path on k+1 vertices or form a directed cycle on k vertices in D. In this introductory paper several properties of P₃(D) are studied, in particular with respect to isomorphism and traversability. In our main results, we characterize all digraphs D with P₃(D) ≅ D, we show that P₃(D₁) ≅ P₃(D₂) "almost always" implies D₁ ≅ D₂, and we characterize all digraphs with Eulerian or Hamiltonian P₃-graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2002, 22, 2; 215-228
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Heavy subgraph pairs for traceability of block-chains
    Autorzy:
    Li, Binlong
    Broersma, Hajo
    Zhang, Shenggui
    Powiązania:
    https://bibliotekanauki.pl/articles/30148234.pdf
    Data publikacji:
    2014-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    block-chain traceable graph
    Ore-type condition
    forbidden subgrap
    $o_{−1}$-heavy subgraph
    Opis:
    A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is $o_{−1}$-heavy if it contains two nonadjacent vertices which satisfy an Ore-type degree condition for traceability, i.e., with degree sum at least $n−1$ in $G$. A block-chain is a graph whose block graph is a path, i.e., it is either a $P_1$, $P_2$, or a 2-connected graph, or a graph with at least one cut vertex and exactly two end-blocks. Obviously, every traceable graph is a block-chain, but the reverse does not hold. In this paper we characterize all the pairs of connected $o_{−1}$-heavy graphs that guarantee traceability of block-chains. Our main result is a common extension of earlier work on degree sum conditions, forbidden subgraph conditions and heavy subgraph conditions for traceability
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 2; 287-307
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A σ₃ type condition for heavy cycles in weighted graphs
    Autorzy:
    Zhang, Shenggui
    Li, Xueliang
    Broersma, Hajo
    Powiązania:
    https://bibliotekanauki.pl/articles/743462.pdf
    Data publikacji:
    2001
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    weighted graph
    (long, heavy, Hamilton) cycle
    weighted degree
    (weighted) degree sum
    Opis:
    A weighted graph is a graph in which each edge e is assigned a non-negative number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges. The weighted degree $d^w(v)$ of a vertex v is the sum of the weights of the edges incident with v. In this paper, we prove the following result: Suppose G is a 2-connected weighted graph which satisfies the following conditions: 1. The weighted degree sum of any three independent vertices is at least m; 2. w(xz) = w(yz) for every vertex z ∈ N(x)∩N(y) with d(x,y) = 2; 3. In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains either a Hamilton cycle or a cycle of weight at least 2m/3. This generalizes a theorem of Fournier and Fraisse on the existence of long cycles in k-connected unweighted graphs in the case k = 2. Our proof of the above result also suggests a new proof to the theorem of Fournier and Fraisse in the case k = 2.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2001, 21, 2; 159-166
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Toughness, Forbidden Subgraphs, and Hamilton-Connected Graphs
    Autorzy:
    Zheng, Wei
    Broersma, Hajo
    Wang, Ligong
    Powiązania:
    https://bibliotekanauki.pl/articles/32361744.pdf
    Data publikacji:
    2022-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    toughness
    forbidden subgraph
    Hamilton-connected graph
    Hamiltonicity
    Opis:
    A graph G is called Hamilton-connected if for every pair of distinct vertices {u, v} of G there exists a Hamilton path in G that connects u and v. A graph G is said to be t-tough if t·ω(G − X) ≤ |X| for all X ⊆ V (G) with ω(G − X) > 1. The toughness of G, denoted τ (G), is the maximum value of t such that G is t-tough (taking τ (Kn) = ∞ for all n ≥ 1). It is known that a Hamilton-connected graph G has toughness τ (G) > 1, but that the reverse statement does not hold in general. In this paper, we investigate all possible forbidden subgraphs H such that every H-free graph G with τ (G) > 1 is Hamilton-connected. We find that the results are completely analogous to the Hamiltonian case: every graph H such that any 1-tough H-free graph is Hamiltonian also ensures that every H-free graph with toughness larger than one is Hamilton-connected. And similarly, there is no other forbidden subgraph having this property, except possibly for the graph K1 ∪ P4 itself. We leave this as an open case.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 1; 187-196
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
    Autorzy:
    Li, Binlong
    Broersma, Hajo J.
    Zhang, Shenggui
    Powiązania:
    https://bibliotekanauki.pl/articles/31340596.pdf
    Data publikacji:
    2016-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    forbidden subgraph
    1-tough graph
    H-free graph
    hamiltonian graph
    Opis:
    A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that every 1-tough H-free graph is hamiltonian. We almost obtain a complete solution to this problem, leaving H = K1 ∪ P4 as the only open case.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 4; 915-929
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
    Autorzy:
    Broersma, Hajo
    Marchal, Bert
    Paulusma, Daniel
    Salman, A.
    Powiązania:
    https://bibliotekanauki.pl/articles/743123.pdf
    Data publikacji:
    2009
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    backbone coloring
    split graph
    matching
    star
    Opis:
    We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring for G and H is a proper vertex coloring V→ {1,2,...} of G in which the colors assigned to adjacent vertices in H differ by at least λ. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers. The main outcome of earlier studies is that the minimum number l of colors, for which such colorings V→ {1,2,...,l} exist, in the worst case is a factor times the chromatic number (for path, tree, matching and star backbones). We show here that for split graphs and matching or star backbones, l is at most a small additive constant (depending on λ) higher than the chromatic number. Our proofs combine algorithmic and combinatorial arguments. We also indicate other graph classes for which our results imply better upper bounds on l than the previously known bounds.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2009, 29, 1; 143-162
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Removable Edges on a Hamilton Cycle or Outside a Cycle in a 4-Connected Graph
    Autorzy:
    Wu, Jichang
    Broersma, Hajo
    Mao, Yaping
    Ma, Qin
    Powiązania:
    https://bibliotekanauki.pl/articles/32083895.pdf
    Data publikacji:
    2021-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    4-connected graph
    removable edge
    fragment
    atom
    Opis:
    Let G be a 4-connected graph. We call an edge e of G removable if the following sequence of operations results in a 4-connected graph: delete e from G; if there are vertices with degree 3 in G−e, then for each (of the at most two) such vertex x, delete x from G − e and turn the three neighbors of x into a clique by adding any missing edges (avoiding multiple edges). In this paper, we continue the study on the distribution of removable edges in a 4-connected graph G, in particular outside a cycle of G or in a spanning tree or on a Hamilton cycle of G. We give examples to show that our results are in some sense best possible.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 2; 559-587
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Heavy cycles in weighted graphs
    Autorzy:
    Bondy, J.
    Broersma, Hajo
    van den Heuvel, Jan
    Veldman, Henk
    Powiązania:
    https://bibliotekanauki.pl/articles/743527.pdf
    Data publikacji:
    2002
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    weighted graph
    (long, optimal, Hamilton) cycle
    (edge-, vertex-)weighting
    weighted degree
    Opis:
    An (edge-)weighted graph is a graph in which each edge e is assigned a nonnegative real number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges, and an optimal cycle is one of maximum weight. The weighted degree w(v) of a vertex v is the sum of the weights of the edges incident with v. The following weighted analogue (and generalization) of a well-known result by Dirac for unweighted graphs is due to Bondy and Fan. Let G be a 2-connected weighted graph such that w(v) ≥ r for every vertex v of G. Then either G contains a cycle of weight at least 2r or every optimal cycle of G is a Hamilton cycle. We prove the following weighted analogue of a generalization of Dirac's result that was first proved by Pósa. Let G be a 2-connected weighted graph such that w(u)+w(v) ≥ s for every pair of nonadjacent vertices u and v. Then G contains either a cycle of weight at least s or a Hamilton cycle. Examples show that the second conclusion cannot be replaced by the stronger second conclusion from the result of Bondy and Fan. However, we characterize a natural class of edge-weightings for which these two conclusions are equivalent, and show that such edge-weightings can be recognized in time linear in the number of edges.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2002, 22, 1; 7-15
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-9 z 9

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies