Skip to main content
Top

2019 | OriginalPaper | Chapter

Graph Functionality

Authors : Bogdan Alecu, Aistis Atminas, Vadim Lozin

Published in: Graph-Theoretic Concepts in Computer Science

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In the present paper, we introduce the notion of graph functionality, which generalizes simultaneously several other graph parameters, such as degeneracy or clique-width, in the sense that bounded degeneracy or bounded clique-width imply bounded functionality. Moreover, we show that this generalization is proper by revealing classes of graphs of unbounded degeneracy and clique-width, where functionality is bounded by a constant. We also prove that bounded functionality implies bounded VC-dimension, i.e. graphs of bounded VC-dimension extend graphs of bounded functionality, and this extension also is proper.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Atminas, A., Collins, A., Lozin, V., Zamaraev, V.: Implicit representations and factorial properties of graphs. Discrete Math. 338, 164–179 (2015)MathSciNetCrossRef Atminas, A., Collins, A., Lozin, V., Zamaraev, V.: Implicit representations and factorial properties of graphs. Discrete Math. 338, 164–179 (2015)MathSciNetCrossRef
2.
go back to reference Alon, N., Brightwell, G., Kierstead, H., Kostochka, A., Winkler, P.: Dominating sets in \(k\)-majority tournaments. J. Comb. Theory Ser. B 96, 374–387 (2006)MathSciNetCrossRef Alon, N., Brightwell, G., Kierstead, H., Kostochka, A., Winkler, P.: Dominating sets in \(k\)-majority tournaments. J. Comb. Theory Ser. B 96, 374–387 (2006)MathSciNetCrossRef
3.
go back to reference Balogh, J., Bollobás, B., Weinreich, D.: The speed of hereditary properties of graphs. J. Comb. Theory Ser. B 79, 131–156 (2000)MathSciNetCrossRef Balogh, J., Bollobás, B., Weinreich, D.: The speed of hereditary properties of graphs. J. Comb. Theory Ser. B 79, 131–156 (2000)MathSciNetCrossRef
5.
go back to reference Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46, 218–270 (1993)MathSciNetCrossRef Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46, 218–270 (1993)MathSciNetCrossRef
6.
go back to reference Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33, 125–150 (2000)MathSciNetCrossRef Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33, 125–150 (2000)MathSciNetCrossRef
7.
8.
go back to reference Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423–443 (2000) MathSciNetCrossRef Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423–443 (2000) MathSciNetCrossRef
10.
go back to reference Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. In: STOC 1988, pp. 334–343 (1988) Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. In: STOC 1988, pp. 334–343 (1988)
11.
go back to reference Lejeune, M., Lozin, V., Lozina, I., Ragab, A., Yacout, S.: Recent advances in the theory and practice of Logical Analysis of Data. Eur. J. Oper. Res. 275, 1–15 (2019)MathSciNetCrossRef Lejeune, M., Lozin, V., Lozina, I., Ragab, A., Yacout, S.: Recent advances in the theory and practice of Logical Analysis of Data. Eur. J. Oper. Res. 275, 1–15 (2019)MathSciNetCrossRef
14.
go back to reference Spinrad, J.P.: Efficient Graph Representations. Fields Institute Monographs, 19, xiii+342 pp. American Mathematical Society, Providence (2003) Spinrad, J.P.: Efficient Graph Representations. Fields Institute Monographs, 19, xiii+342 pp. American Mathematical Society, Providence (2003)
Metadata
Title
Graph Functionality
Authors
Bogdan Alecu
Aistis Atminas
Vadim Lozin
Copyright Year
2019
DOI
https://doi.org/10.1007/978-3-030-30786-8_11

Premium Partner