American Institute of Mathematical Sciences

Advanced
February  2009, 3(1): 97-114. doi: 10.3934/amc.2009.3.97

Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs

David Auger 1, , Irène Charon 1, , Iiro Honkala 2, , Olivier Hudry 1, and  Antoine Lobstein 1,

1. 

Institut TELECOM - TELECOM ParisTech, & Centre National de la Recherche Scientifique - LTCI UMR 5141, 46, rue Barrault, 75634 Paris Cedex 13, France
2. 

Department of Mathematics, University of Turku, 20014 Turku, Finland

Received  November 2008 Revised  January 2009 Published  January 2009

Consider a connected, undirected graph $G=(V,E)$ and an integer $r \geq 1$; for any vertex $v\in V$, let $B_r(v)$ denote the ball of radius $r$ centred at $v$, i.e., the set of all vertices linked to $v$ by a path consisting of at most $r$ edges. If for all vertices $v \in V$, the sets $B_r(v)$ are different, then we say that $G$ is $r$-twin-free.
In $r$-twin-free graphs, we prolong the study of the extremal values that can be achieved by the main classical parameters in graph theory, and investigate here the number of edges, the minimum degree, the size of a maximum independent set, as well as radius and diameter.
Keywords: identifying code, maximum stable set, maximum independent set, identifiable graph, minimum degree, Graph theory, twin-free graph, diameter., twins, radius.
Mathematics Subject Classification: Primary: 05C99; Secondary: 05C3.
Citation: David Auger, Irène Charon, Iiro Honkala, Olivier Hudry, Antoine Lobstein. Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs. Advances in Mathematics of Communications, 2009, 3 (1) : 97-114. doi: 10.3934/amc.2009.3.97
[1]

Kongzhi Li, Xiaoping Xue. The Łojasiewicz inequality for free energy functionals on a graph. Communications on Pure and Applied Analysis, 2022, 21 (8) : 2661-2677. doi: 10.3934/cpaa.2022066
[2]

Mirela Domijan, Markus Kirkilionis. Graph theory and qualitative analysis of reaction networks. Networks and Heterogeneous Media, 2008, 3 (2) : 295-322. doi: 10.3934/nhm.2008.3.295
[3]

M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks and Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201
[4]

M. A. Efendiev. On the compactness of the stable set for rate independent processes. Communications on Pure and Applied Analysis, 2003, 2 (4) : 495-509. doi: 10.3934/cpaa.2003.2.495
[5]

Wei Gao, Juan Luis García Guirao, Mahmoud Abdel-Aty, Wenfei Xi. An independent set degree condition for fractional critical deleted graphs. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 877-886. doi: 10.3934/dcdss.2019058
[6]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[7]

Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17
[8]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413
[9]

John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.

[10]

Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5243-5269. doi: 10.3934/dcds.2021075
[11]

Barton E. Lee. Consensus and voting on large graphs: An application of graph limit theory. Discrete and Continuous Dynamical Systems, 2018, 38 (4) : 1719-1744. doi: 10.3934/dcds.2018071
[12]

Roy H. Goodman. NLS bifurcations on the bowtie combinatorial graph and the dumbbell metric graph. Discrete and Continuous Dynamical Systems, 2019, 39 (4) : 2203-2232. doi: 10.3934/dcds.2019093
[13]

Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete and Continuous Dynamical Systems, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261
[14]

Rui Wang, Rundong Zhao, Emily Ribando-Gros, Jiahui Chen, Yiying Tong, Guo-Wei Wei. HERMES: Persistent spectral graph software. Foundations of Data Science, 2021, 3 (1) : 67-97. doi: 10.3934/fods.2021006
[15]

Dominique Zosso, Braxton Osting. A minimal surface criterion for graph partitioning. Inverse Problems and Imaging, 2016, 10 (4) : 1149-1180. doi: 10.3934/ipi.2016036
[16]

Mario Jorge Dias Carneiro, Rafael O. Ruggiero. On the graph theorem for Lagrangian minimizing tori. Discrete and Continuous Dynamical Systems, 2018, 38 (12) : 6029-6045. doi: 10.3934/dcds.2018260
[17]

A. C. Eberhard, J-P. Crouzeix. Existence of closed graph, maximal, cyclic pseudo-monotone relations and revealed preference theory. Journal of Industrial and Management Optimization, 2007, 3 (2) : 233-255. doi: 10.3934/jimo.2007.3.233
[18]

Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure and Applied Analysis, 2021, 20 (2) : 885-902. doi: 10.3934/cpaa.2020295
[19]

Chun-Xiang Guo, Guo Qiang, Jin Mao-Zhu, Zhihan Lv. Dynamic systems based on preference graph and distance. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1139-1154. doi: 10.3934/dcdss.2015.8.1139
[20]

Liu Hui, Lin Zhi, Waqas Ahmad. Network(graph) data research in the coordinate system. Mathematical Foundations of Computing, 2018, 1 (1) : 1-10. doi: 10.3934/mfc.2018001

2021 Impact Factor: 1.015

Tools

Metrics

  • PDF downloads (110)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy