Temat: Homomorphism - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Distinguishing graphs by the number of homomorphisms
Autorzy:: Fisk, Steve
Powiązania:: https://bibliotekanauki.pl/articles/971917.pdf
Data publikacji:: 1995
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph homomorphism
chromatic number
Opis:: A homomorphism from one graph to another is a map that sends vertices to vertices and edges to edges. We denote the number of homomorphisms from G to H by |G → H|. If is a collection of graphs, we say that distinguishes graphs G and H if there is some member X of such that |G → X | ≠ |H → X|. is a distinguishing family if it distinguishes all pairs of graphs.
We show that various collections of graphs are a distinguishing family.
Źródło:: Discussiones Mathematicae Graph Theory; 1995, 15, 1; 73-75
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Cryptography with right-angled Artin groups
Autorzy:: Flores, R.
Kahrobaei, D.
Powiązania:: https://bibliotekanauki.pl/articles/375820.pdf
Data publikacji:: 2016
Wydawca:: Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:: authentication schemes
group homomorphism
graph homomorphism
schematy uwierzytelniania
homomorfizm grup
homeomorfizm grafów
Opis:: In this paper we propose right-angled Artin groups as a platform for secret sharing schemes based on the efficiency (linear time) of the word problem. Inspired by previous work of Grigoriev-Shpilrain in the context of graphs, we define two new problems: Subgroup Isomorphism Problem and Group Homomorphism Problem. Based on them, we also propose two new authentication schemes. For right-angled Artin groups, the Group Homomorphism and Graph Homomorphism problems are equivalent, and the later is known to be NP-complete. In the case of the Subgroup Isomorphism problem, we bring some results due to Bridson who shows there are right-angled Artin groups in which this problem is unsolvable.
Źródło:: Theoretical and Applied Informatics; 2016, 28, 3; 8-16
1896-5334
Pojawia się w:: Theoretical and Applied Informatics
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: Partial covers of graphs
Autorzy:: Fiala, Jirí
Kratochvíl, Jan
Powiązania:: https://bibliotekanauki.pl/articles/743545.pdf
Data publikacji:: 2002
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: covering projection
computational complexity
graph homomorphism
Opis:: Given graphs G and H, a mapping f:V(G) → V(H) is a homomorphism if (f(u),f(v)) is an edge of H for every edge (u,v) of G. In this paper, we initiate the study of computational complexity of locally injective homomorphisms called partial covers of graphs. We motivate the study of partial covers by showing a correspondence to generalized (2,1)-colorings of graphs, the notion stemming from a practical problem of assigning frequencies to transmitters without interference. We compare the problems of deciding existence of partial covers and of full covers (locally bijective homomorphisms), which were previously studied.
Źródło:: Discussiones Mathematicae Graph Theory; 2002, 22, 1; 89-99
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: Families of strongly projective graphs
Autorzy:: Larose, Benoit
Powiązania:: https://bibliotekanauki.pl/articles/743360.pdf
Data publikacji:: 2002
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: distance-transitive graphs
graph homomorphism
graph product
Opis:: We give several characterisations of strongly projective graphs which generalise in many respects odd cycles and complete graphs [7]. We prove that all known families of projective graphs contain only strongly projective graphs, including complete graphs, odd cycles, Kneser graphs and non-bipartite distance-transitive graphs of diameter d ≥ 3.
Źródło:: Discussiones Mathematicae Graph Theory; 2002, 22, 2; 271-292
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 5.

Tytuł:: More on linear and metric tree maps
Autorzy:: Kozerenko, Sergiy
Powiązania:: https://bibliotekanauki.pl/articles/1397335.pdf
Data publikacji:: 2021
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: Markov graph
metric map
non-expanding map
linear map
graph homomorphism
Opis:: We consider linear and metric self-maps on vertex sets of finite combinatorial trees. Linear maps are maps which preserve intervals between pairs of vertices whereas metric maps are maps which do not increase distances between pairs of vertices. We obtain criteria for a given linear or a metric map to be a positive (negative) under some orientation of the edges in a tree, we characterize trees which admit maps with Markov graphs being paths and prove that the converse of any partial functional digraph is isomorphic to a Markov graph for some suitable map on a tree.
Źródło:: Opuscula Mathematica; 2021, 41, 1; 55-70
1232-9274
2300-6919
Pojawia się w:: Opuscula Mathematica
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja