Temat: complete bipartite graph - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Decompositions of Complete Bipartite Graphs and Complete Graphs Into Paths, Stars, and Cycles with Four Edges Each
Autorzy:: Shyu, Tay-Woei
Powiązania:: https://bibliotekanauki.pl/articles/32083883.pdf
Data publikacji:: 2021-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: complete graph
complete bipartite graph
path
star
cycle
decomposition
Opis:: Let G be either a complete graph of odd order or a complete bipartite graph in which each vertex partition has an even number of vertices. In this paper, we determine the set of triples (p, q, r), with p, q, r > 0, for which there exists a decomposition of G into p paths, q stars, and r cycles, each of which has 4 edges.
Źródło:: Discussiones Mathematicae Graph Theory; 2021, 41, 2; 451-468
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: On 2-periodic graphs of a certain graph operator
Autorzy:: Havel, Ivan
Zelinka, Bohdan
Powiązania:: https://bibliotekanauki.pl/articles/743413.pdf
Data publikacji:: 2001
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph operator
power and complement of a graph
Desarguesian finite projective geometry
decomposition of a complete bipartite graph
generalized hypercube
Opis:: We deal with the graph operator $\overline{Pow₂}$ defined to be the complement of the square of a graph: $\overline{Pow₂}(G) = \overline{Pow₂(G)}$. Motivated by one of many open problems formulated in [6] we look for graphs that are 2-periodic with respect to this operator. We describe a class of bipartite graphs possessing the above mentioned property and prove that for any m,n ≥ 6, the complete bipartite graph $K_{m,n}$ can be decomposed in two edge-disjoint factors from . We further show that all the incidence graphs of Desarguesian finite projective geometries belong to and find infinitely many graphs also belonging to among generalized hypercubes.
Źródło:: Discussiones Mathematicae Graph Theory; 2001, 21, 1; 13-30
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: Optimal edge ranking of complete bipartite graphs in polynomial time
Autorzy:: Hung, Ruo-Wei
Powiązania:: https://bibliotekanauki.pl/articles/743901.pdf
Data publikacji:: 2006
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph algorithms
edge ranking
vertex ranking
edge-separator tree
complete bipartite graphs
Opis:: An edge ranking of a graph is a labeling of edges using positive integers such that all paths connecting two edges with the same label visit an intermediate edge with a higher label. An edge ranking of a graph is optimal if the number of labels used is minimum among all edge rankings. As the problem of finding optimal edge rankings for general graphs is NP-hard [12], it is interesting to concentrate on special classes of graphs and find optimal edge rankings for them efficiently. Apart from trees and complete graphs, little has been known about special classes of graphs for which the problem can be solved in polynomial time. In this paper, we present a polynomial-time algorithm to find an optimal edge ranking for a complete bipartite graph by using the dynamic programming strategy.
Źródło:: Discussiones Mathematicae Graph Theory; 2006, 26, 1; 149-159
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: The Complexity of Secure Domination Problem in Graphs
Autorzy:: Wang, Haichao
Zhao, Yancai
Deng, Yunping
Powiązania:: https://bibliotekanauki.pl/articles/31342335.pdf
Data publikacji:: 2018-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: secure domination
star convex bipartite graph
doubly chordal graph
NP-complete
APX-complete
Opis:: A dominating set of a graph G is a subset D ⊆ V (G) such that every vertex not in D is adjacent to at least one vertex in D. A dominating set S of G is called a secure dominating set if each vertex u ∈ V (G) \ S has one neighbor v in S such that (S \ {v}) ∪ {u} is a dominating set of G. The secure domination problem is to determine a minimum secure dominating set of G. In this paper, we first show that the decision version of the secure domination problem is NP-complete for star convex bipartite graphs and doubly chordal graphs. We also prove that the secure domination problem cannot be approximated within a factor of (1−ε) ln |V | for any ε > 0, unless NP⊆DTIME (|V |^{O(log log |V|})). Finally, we show that the secure domination problem is APX-complete for bounded degree graphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2018, 38, 2; 385-396
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja