A note on the density of the strong product of graphs

• Autorzy: Pikies T.

Warianty tytułu

PL

Przyczynek do gęstości silnego produktu grafów

• Języki publikacji: EN

Abstrakty

EN

This paper presents some lower and upper bounds on the density of a graph in its strong powers. They were created using the basic graph parameters and using basic properties of the strong product. The created bounds were sufficient to make a general conclusion about how the density in the strong powers of a graph behaves. On the basis of these considerations a simple conclusion follows on the merit of graph algorithms sensitive to the number of edges for applications to this type of graphs.

PL

Praca zawiera pewne dolne oraz górne ograniczenia dla gęstości silnych potęg grafu. Zostały one wyznaczone przy pomocy podstawowych parametrów grafu oraz podstawowych własności silnego produktu. Wyznaczone ograniczenia są wystarczające do wysnucia prostych wniosków odnośnie zachowanie gęstości w silnych potęgach grafu. Wnioski te świadczą o zasadności stosowania algorytmów wrażliwych na ilość krawędzi przy badaniu silnych potęg grafów.

Słowa kluczowe

EN

graphs; destiny

PL

gęstość; grafy

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2018
• Tom: T. 23
• Strony: 97--103
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Pikies T.

• Department of Algorithms and System Modelling, Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology

Bibliografia

• [1] Casablanca R. M.: Reliability of Networks Modelled by Graph Products, Ph.D. dissertation, Department of Applied Mathematics I, University of Seville, Seville, Spain, 2014.
• [2] Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.: Introduction to Algorithms, Second Edition, MIT Press, 2001.
• [3] Mucha M., Sankowski P.: Maximum matchings via gaussian elimination. IEEE Annual Symposium on Foundations of Computer Science, 2004.
• [4] Vazirani V. V.: A proof of the MV matching algorithm,
• [5] https://www.cc.gatech.edu/fac/Vijay.Vazirani/new-proof.pdf, 2014.